• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/TCO22-3-U/1A.cpp version [9e9e901ef52d9c72]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class TwoDimensionalSort { public:
           23  + vector <int> sortLetters(vector <string> board)
           24  + {
           25  +  vector<int> ans;
           26  +  int next_x = 0;
           27  +  for (int y = 0; y < 26; ++y) {
           28  +   int np = 26 - count(board[y].begin(), board[y].end(), '.');
           29  +   // shift to [next_x .. next_x+np)
           30  +   for (;;) {
           31  +    int done = 0;
           32  +    for (int x = 0, i = 0; x < 26; ++x) {
           33  +     if (board[y][x] != '.') {
           34  +      int xx = next_x + i;
           35  +      if (xx == x)
           36  +       done++;
           37  +      else if(board[y][xx]=='.'){
           38  +       int l = min(x, xx) + 1;
           39  +       int r = max(x, xx);
           40  +       if (count(board[y].begin() + l, board[y].begin() + r, '.') == r - l) {
           41  +        ans.push_back(y);
           42  +        ans.push_back(x);
           43  +        ans.push_back(y);
           44  +        ans.push_back(xx);
           45  +        board[y][xx] = board[y][x];
           46  +        board[y][x] = '.';
           47  +        break;
           48  +       }
           49  +      }
           50  +      ++i;
           51  +     }
           52  +    }
           53  +    if (done == np)
           54  +     break;
           55  +   }
           56  +   next_x += np;
           57  +  }
           58  +
           59  +  for (int y = 0; y < 26; ++y) {
           60  +   for (int x = 0; x < 26; ++x) {
           61  +    if (board[y][x] != '.') {
           62  +     int yy = board[y][x] - 'A';
           63  +     if (y != yy) {
           64  +      ans.push_back(y);
           65  +      ans.push_back(x);
           66  +      ans.push_back(yy);
           67  +      ans.push_back(x);
           68  +     }
           69  +    }
           70  +   }
           71  +  }
           72  +  cerr << ans.size() / 4 << endl;
           73  +  return ans;
           74  + }
           75  +};
           76  +
           77  +// BEGIN CUT HERE
           78  +#include <ctime>
           79  +double start_time; string timer()
           80  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           81  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           82  + { os << "{ ";
           83  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           84  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           85  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           86  + bool ok = (Expected == Received);
           87  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           88  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           89  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           90  +#define END  verify_case(_, TwoDimensionalSort().sortLetters(board));}
           91  +int main(){
           92  +
           93  +CASE(0)
           94  + string board_[] = {"..........................",
           95  + "..........................",
           96  + "..........................",
           97  + "..........................",
           98  + "..........................",
           99  + "..........................",
          100  + "..........................",
          101  + "..........................",
          102  + "..........................",
          103  + "..........................",
          104  + "..........................",
          105  + "..........................",
          106  + "..........................",
          107  + "..........................",
          108  + "..........................",
          109  + "..........................",
          110  + "..........................",
          111  + "..........................",
          112  + "..........................",
          113  + "..........................",
          114  + "..........................",
          115  + "..........................",
          116  + "..........................",
          117  + "..........................",
          118  + "..........................",
          119  + ".........................."};
          120  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          121  + vector <int> _;
          122  +END
          123  +CASE(1)
          124  + string board_[] = {"..........................",
          125  + "..........................",
          126  + "......B...................",
          127  + "..............Q...........",
          128  + "..........................",
          129  + "..........................",
          130  + "..........................",
          131  + "..........................",
          132  + "..........................",
          133  + "..........................",
          134  + "..........................",
          135  + "..........................",
          136  + "..........................",
          137  + "..........................",
          138  + "..........................",
          139  + "..........................",
          140  + "..........................",
          141  + "..........................",
          142  + "..........................",
          143  + "..........................",
          144  + "..........................",
          145  + "..........................",
          146  + "..........................",
          147  + "..........................",
          148  + "..........................",
          149  + ".........................."};
          150  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          151  + int __[] = {3, 14, 3, 17 };
          152  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          153  +END
          154  +CASE(2)
          155  + string board_[] = {"..........................",
          156  + "..........................",
          157  + "..........................",
          158  + ".....BCDE.................",
          159  + ".....F....................",
          160  + ".....G.A..................",
          161  + ".....H....................",
          162  + "..........................",
          163  + "..........................",
          164  + "..........................",
          165  + "..........................",
          166  + "..........................",
          167  + "..........................",
          168  + "..........................",
          169  + "..........................",
          170  + "..........................",
          171  + "..........................",
          172  + "..........................",
          173  + "..........................",
          174  + "..........................",
          175  + "..........................",
          176  + "..........................",
          177  + "..........................",
          178  + "..........................",
          179  + "..........................",
          180  + ".........................."};
          181  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          182  + int __[] = {5, 7, 5, 9, 5, 9, 2, 9 };
          183  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          184  +END
          185  +CASE(3)
          186  + string board_[] = {"..........................",
          187  + "..........................",
          188  + "..........................",
          189  + ".....BCED.................",
          190  + ".....F....................",
          191  + ".....G.A..................",
          192  + ".....H....................",
          193  + "..........................",
          194  + "..........................",
          195  + "..........................",
          196  + "..........................",
          197  + "..........................",
          198  + "..........................",
          199  + "..........................",
          200  + "..........................",
          201  + "..........................",
          202  + "..........................",
          203  + "..........................",
          204  + "..........................",
          205  + "..........................",
          206  + "..........................",
          207  + "..........................",
          208  + "..........................",
          209  + "..........................",
          210  + "..........................",
          211  + ".........................."};
          212  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          213  + int __[] = {3, 7, 2, 7, 2, 7, 2, 11, 5, 7, 0, 7, 2, 11, 3, 11 };
          214  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          215  +   END
          216  +    CASE(4)
          217  +    string board_[] = {
          218  +      "..........................",
          219  +      "..........................",
          220  +      "..........................",
          221  +      "..........................",
          222  +      "..............P...........",
          223  +      "..............Q...........",
          224  +      "..............N...........",
          225  +      "..............X...........",
          226  +      "..............E...........",
          227  +      "..............H...........",
          228  +      "..............L...........",
          229  +      "..............O...........",
          230  +      "..............J...........",
          231  +      "..............B...........",
          232  +      "..............Y...........",
          233  +      "..............A...........",
          234  +      "..............T...........",
          235  +      "..............I...........",
          236  +      "..............D...........",
          237  +      "..............G...........",
          238  +      "..............U...........",
          239  +      "..............S...........",
          240  +      "..............K...........",
          241  +      "..............C...........",
          242  +      "..........................",
          243  +      ".........................." };
          244  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          245  +   int __[] = { -1 };
          246  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          247  +END
          248  +/*
          249  +CASE(5)
          250  + string board_[] = ;
          251  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          252  + int __[] = ;
          253  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          254  +END
          255  +*/
          256  +}
          257  +// END CUT HERE