Overview
| SHA1 Hash: | f1d5bbf0f52558dbeecb7cde6de6cf902b2a6387 |
|---|---|
| Date: | 2012-08-04 13:45:46 |
| User: | kinaba |
| Comment: | 550 |
| Timelines: | family | ancestors | descendants | both | 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/550-U/1A.cpp version [463196d9224d114a]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class RotatingBot { public: > 23 int minArea(vector <int> moves) > 24 { > 25 if( moves.size() == 1 ) { > 26 int w = moves[0]+1; > 27 return w; > 28 } > 29 if( moves.size() == 2 ) { > 30 int w = moves[0]+1; > 31 int h = moves[1]+1; > 32 return w*h; > 33 } > 34 if( moves.size() == 3 ) { > 35 int w1 = moves[0]+1; > 36 int h = moves[1]+1; > 37 int w2 = moves[2]+1; > 38 return max(w1,w2)*h; > 39 } > 40 if( moves.size() == 4 ) { > 41 int w1 = moves[0]+1; > 42 int h1 = moves[1]+1; > 43 int w2 = moves[2]+1; > 44 int h2 = moves[3]+1; > 45 if( w1 > w2 ) > 46 return -1; > 47 if( w1 == w2 ) { > 48 if( h1 <= h2 ) > 49 return -1; > 50 else > 51 return w1*h1; > 52 } > 53 return w2*max(h1,h2); > 54 } > 55 > 56 int w1 = moves[0]+1; > 57 int h1 = moves[1]+1; > 58 int w2 = moves[2]+1; > 59 int h2 = moves[3]+1; > 60 if( w1 > w2 ) > 61 return -1; > 62 if( w1 == w2 ) { > 63 vector<int> rm = simulate(w1, h1, 0, 0); > 64 if( match(rm, moves) ) > 65 return w1*h1; > 66 else > 67 return -1; > 68 } else { > 69 if( h2<h1 ) > 70 return -1; > 71 vector<int> rm = simulate(w2, h2, w2-w1, h2-h1); > 72 if( match(rm, moves) ) > 73 return w2*h2; > 74 else > 75 return -1; > 76 } > 77 } > 78 > 79 vector<int> simulate(int w, int h, int x, int y) > 80 { > 81 vector<int> moves; > 82 vector< vector<bool> > vis(h, vector<bool>(w)); > 83 int dx[]={+1,0,-1,0}; > 84 int dy[]={0,+1,0,-1}; > 85 int d = 0; > 86 vis[y][x] = true; > 87 for(;;) { > 88 int cnt = 0; > 89 for(;;) { > 90 int xx=x+dx[d]; > 91 int yy=y+dy[d]; > 92 if( yy<0||h<=yy||xx<0||w<=xx||vis[yy][xx] ) > 93 break; > 94 y=yy, x=xx; > 95 vis[y][x] = true; > 96 ++cnt; > 97 } > 98 d = (d+1)%4; > 99 if( cnt == 0 ) > 100 break; > 101 moves.push_back(cnt); > 102 } > 103 return moves; > 104 } > 105 > 106 bool match(const vector<int>& rm, const vector<int>& m) > 107 { > 108 if(rm.size() < m.size()) > 109 return false; > 110 for(int i=0; i+1<m.size(); ++i) > 111 if(rm[i] != m[i]) > 112 return false; > 113 return rm[m.size()-1] >= m[m.size()-1]; > 114 } > 115 }; > 116 > 117 // BEGIN CUT HERE > 118 #include <ctime> > 119 double start_time; string timer() > 120 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 121 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 122 { os << "{ "; > 123 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 124 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 125 void verify_case(const int& Expected, const int& Received) { > 126 bool ok = (Expected == Received); > 127 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 128 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 129 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 130 #define END verify_case(_, RotatingBot().minArea(moves));} > 131 int main(){ > 132 > 133 CASE(0) > 134 int moves_[] = {15}; > 135 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 136 int _ = 16; > 137 END > 138 CASE(1) > 139 int moves_[] = {3,10}; > 140 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 141 int _ = 44; > 142 END > 143 CASE(2) > 144 int moves_[] = {1,1,1,1}; > 145 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 146 int _ = -1; > 147 END > 148 CASE(3) > 149 int moves_[] = {9,5,11,10,11,4,10}; > 150 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 151 int _ = 132; > 152 END > 153 CASE(4) > 154 int moves_[] = {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19 > 155 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 156 int _ = 420; > 157 END > 158 CASE(5) > 159 int moves_[] = {8,6,6,1}; > 160 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 161 int _ = -1; > 162 END > 163 CASE(6) > 164 int moves_[] = {8,6,6}; > 165 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 166 int _ = 63; > 167 END > 168 CASE(7) > 169 int moves_[] = {5,4,5,3,3}; > 170 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 171 int _ = 30; > 172 END > 173 CASE(8) > 174 int moves_[] = {2,2,2,1}; > 175 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 176 int _ = 9; > 177 END > 178 /* > 179 CASE(9) > 180 int moves_[] = ; > 181 vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); > 182 int _ = ; > 183 END > 184 */ > 185 } > 186 // END CUT HERE
Added SRM/550-U/1B.cpp version [5862d1075889b63d]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class CheckerExpansion { public: > 23 vector <string> resultAfter(long long t, long long x0, long long y0, int > 24 { > 25 vector<string> answer(h, string(w, '.')); > 26 for(int y_=0; y_<h; ++y_) > 27 for(int x_=0; x_<w; ++x_) { > 28 LL y = y0 + y_; > 29 LL x = x0 + x_; > 30 if( (y+x)%2==1 ) > 31 continue; > 32 LL N = (y+x)/2; > 33 if( t <= N ) > 34 continue; > 35 LL k = x-N; > 36 if( k<0 || N<k ) > 37 continue; > 38 if( is_comb_odd(N,k) ) > 39 answer[h-y_-1][x_] = (N%2==0 ? 'A' : 'B'); > 40 } > 41 return answer; > 42 } > 43 > 44 bool is_comb_odd(LL n, LL k) > 45 { > 46 for(LL m=1; m<=n; m<<=1) > 47 if( (k&m) && !(n&m) ) > 48 return false; > 49 return true; > 50 } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 62 bool ok = (Expected == Received); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, CheckerExpansion().resultAfter(t, x0, y0, w, h)) > 67 int main(){ > 68 > 69 CASE(0) > 70 long long t = 1LL; > 71 long long x0 = 0LL; > 72 long long y0 = 0LL; > 73 int w = 4; > 74 int h = 4; > 75 string __[] = {"....", "....", "....", "A..." }; > 76 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 77 END > 78 CASE(1) > 79 long long t = 5LL; > 80 long long x0 = 4LL; > 81 long long y0 = 1LL; > 82 int w = 3; > 83 int h = 4; > 84 string __[] = {"A..", "...", "B..", ".B." }; > 85 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 86 END > 87 CASE(2) > 88 long long t = 1024LL; > 89 long long x0 = 1525LL; > 90 long long y0 = 512LL; > 91 int w = 20; > 92 int h = 2; > 93 string __[] = {"B...B...B...........", ".B.A.B.A.B.........." }; > 94 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 95 END > 96 CASE(3) > 97 long long t = 53LL; > 98 long long x0 = 85LL; > 99 long long y0 = 6LL; > 100 int w = 5; > 101 int h = 14; > 102 string __[] = {".....", ".....", "B....", ".B.A.", ".....", ".....", ".. > 103 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 104 END > 105 CASE(4) > 106 long long t = 1000000000000LL; > 107 long long x0 = 1000000000000LL; > 108 long long y0 = 123456789123LL; > 109 int w = 50; > 110 int h = 50; > 111 string __[] = {"?"}; > 112 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 113 END > 114 /* > 115 CASE(5) > 116 long long t = LL; > 117 long long x0 = LL; > 118 long long y0 = LL; > 119 int w = ; > 120 int h = ; > 121 string __[] = ; > 122 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 123 END > 124 */ > 125 } > 126 // END CUT HERE