Overview
| SHA1 Hash: | fa7992ffc586d0b5cb1420a581577c155a617d66 |
|---|---|
| Date: | 2012-08-06 15:26:11 |
| User: | kinaba |
| Comment: | 550 done |
| 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
Deleted 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 <
Deleted 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 <
Deleted SRM/550-U/1C.cpp version [b366e6f6edd62cdd]
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 static const int MODVAL = 1000000007; < 23 struct mint < 24 { < 25 int val; < 26 mint():val(0){} < 27 mint(int x):val(x%MODVAL) {} < 28 mint(size_t x):val(x%MODVAL) {} < 29 mint(LL x):val(x%MODVAL) {} < 30 }; < 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } < 32 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } < 33 mint operator+(mint x, mint y) { return x+=y; } < 34 mint operator*(mint x, mint y) { return x*=y; } < 35 < 36 template<typename T> < 37 vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) < 38 { < 39 int N = a.size(); < 40 vector<T> u(N); < 41 for(int i=0; i<N; ++i) < 42 for(int j=0; j<N; ++j) < 43 u[i] += a[i][j]*v[j]; < 44 return u; < 45 } < 46 < 47 template<typename T> < 48 vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> < 49 { < 50 int N = a.size(); < 51 vector< vector<T> > c(N, vector<T>(N)); < 52 for(int i=0; i<N; ++i) < 53 for(int j=0; j<N; ++j) < 54 for(int k=0; k<N; ++k) < 55 c[i][j] += a[i][k]*b[k][j]; < 56 return c; < 57 } < 58 < 59 template<typename T> < 60 vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) < 61 { < 62 int N = a.size(); < 63 vector< vector<T> > c(N, vector<T>(N)); < 64 for(int i=0; i<N; ++i) c[i][i] = 1; < 65 for(; e; e>>=1) { < 66 if(e&1) < 67 c = MATMUL(c, a); < 68 a = MATMUL(a, a); < 69 } < 70 return c; < 71 } < 72 < 73 class ConversionMachine { public: < 74 int countAll(string word1, string word2, vector <int> costs, int maxCost < 75 { < 76 int d[3] = {}; < 77 LL minCost = 0; < 78 for(int i=0; i<word1.size(); ++i) { < 79 int dd=0; < 80 while( word1[i] != word2[i] ) { < 81 dd += 1; < 82 minCost += costs[word1[i]-'a']; < 83 word1[i] = (word1[i]+1-'a')%3 + 'a'; < 84 } < 85 d[dd] += 1; < 86 } < 87 < 88 if( minCost > maxCost ) < 89 return 0; < 90 LL c3 = accumulate(costs.begin(), costs.end(), 0LL); < 91 return solve(d, (maxCost-minCost)/c3*3+d[1]*1+d[2]*2).val; < 92 } < 93 < 94 mint solve(int d[3], int rem) < 95 { < 96 int n = d[0]+d[1]+d[2]; < 97 < 98 map<pair<int,int>, int> enc; < 99 for(int b=0,id=0; b<=n; ++b) < 100 for(int c=0; b+c<=n; ++c,++id) < 101 enc[make_pair(b,c)] = id; < 102 int D = enc.size(); < 103 < 104 vector< vector<mint> > M(D+1, vector<mint>(D+1)); < 105 for(int b=0; b<=n; ++b) < 106 for(int c=0; b+c<=n; ++c) < 107 { < 108 int a = n-b-c; < 109 if(a) { < 110 M[enc[make_pair(b,c+1)]][enc[make_pair(b,c)]] = < 111 } < 112 if(b) { < 113 M[enc[make_pair(b-1,c)]][enc[make_pair(b,c)]] = < 114 if(b-1==0 && c==0) < 115 M.back()[enc[make_pair(b,c)]] = b; < 116 } < 117 if(c) { < 118 M[enc[make_pair(b+1,c-1)]][enc[make_pair(b,c)]] < 119 } < 120 } < 121 M.back().back() = 1; < 122 < 123 vector<mint> V(D+1); < 124 V[enc[make_pair(d[1],d[2])]] = 1; < 125 V.back() = V[0]; < 126 < 127 return MATMUL(MATPOW(M, rem), V).back(); < 128 } < 129 }; < 130 < 131 // BEGIN CUT HERE < 132 #include <ctime> < 133 double start_time; string timer() < 134 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 135 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 136 { os << "{ "; < 137 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 138 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 139 void verify_case(const int& Expected, const int& Received) { < 140 bool ok = (Expected == Received); < 141 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 142 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 143 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 144 #define END verify_case(_, ConversionMachine().countAll(word1, word2, costs < 145 int main(){ < 146 < 147 CASE(0) < 148 string word1 = "a"; < 149 string word2 = "b"; < 150 int costs_[] = {100,2,3}; < 151 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 152 int maxCost = 205; < 153 int _ = 2; < 154 END < 155 CASE(1) < 156 string word1 = "abcba"; < 157 string word2 = "abcba"; < 158 int costs_[] = {67,23,43}; < 159 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 160 int maxCost = 0; < 161 int _ = 1; < 162 END < 163 CASE(2) < 164 string word1 = "cccccccc"; < 165 string word2 = "aaaaaaaa"; < 166 int costs_[] = {10000000,1,1}; < 167 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 168 int maxCost = 100; < 169 int _ = 40320; < 170 END < 171 CASE(3) < 172 string word1 = "aa"; < 173 string word2 = "cc"; < 174 int costs_[] = {1,10,100}; < 175 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 176 int maxCost = 1787; < 177 int _ = 123611681; < 178 END < 179 /* < 180 CASE(4) < 181 string word1 = ; < 182 string word2 = ; < 183 int costs_[] = ; < 184 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 185 int maxCost = ; < 186 int _ = ; < 187 END < 188 CASE(5) < 189 string word1 = ; < 190 string word2 = ; < 191 int costs_[] = ; < 192 vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); < 193 int maxCost = ; < 194 int _ = ; < 195 END < 196 */ < 197 } < 198 // END CUT HERE <
Name change from from SRM/550-U/1A.cpp to SRM/550/1A.cpp.
Name change from from SRM/550-U/1B.cpp to SRM/550/1B.cpp.
Name change from from SRM/550-U/1C.cpp to SRM/550/1C.cpp.