Overview
| SHA1 Hash: | 52a9b915ea05b5ec41dd3a26e5d9e0f5e8173401 |
|---|---|
| Date: | 2022-07-08 00:46:34 |
| User: | kinaba |
| Comment: | TCO22-R3 |
| Timelines: | family | ancestors | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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 > 41 ans.push_back(y) > 42 ans.push_back(x) > 43 ans.push_back(y) > 44 ans.push_back(xx > 45 board[y][xx] = b > 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) > 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 > 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() > 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