Overview
| SHA1 Hash: | b9612fa18c1e260c7d3a0976a25e8d8bd5242be9 |
|---|---|
| Date: | 2014-04-19 14:28:02 |
| User: | kinaba |
| Comment: | 616 |
| 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/616-U/1A.cpp version [c57ee03e6f42aff8]
> 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 AmebaDiv1 { public: > 23 int count(vector <int> X) > 24 { > 25 set<int> last(X.begin(), X.end()); > 26 int cnt = 0; > 27 for(int E : last) > 28 if(!can_end_by(X, E)) > 29 ++cnt; > 30 return cnt; > 31 } > 32 > 33 bool can_end_by(const vector<int>& X, int E) > 34 { > 35 for(int B=E;;) { > 36 if(run(B, X) == E) > 37 return true; > 38 > 39 if(B%2==0) > 40 B/=2; > 41 else > 42 break; > 43 } > 44 return false; > 45 } > 46 > 47 int run(int B, const vector<int>& X) > 48 { > 49 for(int x: X) > 50 B = (x==B ? B*2 : B); > 51 return B; > 52 } > 53 }; > 54 > 55 // BEGIN CUT HERE > 56 #include <ctime> > 57 double start_time; string timer() > 58 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 59 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 60 { os << "{ "; > 61 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 62 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 63 void verify_case(const int& Expected, const int& Received) { > 64 bool ok = (Expected == Received); > 65 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 66 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 67 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 68 #define END verify_case(_, AmebaDiv1().count(X));} > 69 int main(){ > 70 > 71 CASE(0) > 72 int X_[] = {3,2,1}; > 73 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 74 int _ = 2; > 75 END > 76 CASE(1) > 77 int X_[] = {2,2,2,2,2,2,4,2,2,2}; > 78 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 79 int _ = 2; > 80 END > 81 CASE(2) > 82 int X_[] = {1,2,4,8,16,32,64,128,256,1024,2048}; > 83 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 84 int _ = 11; > 85 END > 86 CASE(3) > 87 int X_[] = {854,250,934,1000,281,250,281,467,854,562,934,1000,854,500,56 > 88 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 89 int _ = 7; > 90 END > 91 /* > 92 CASE(4) > 93 int X_[] = ; > 94 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 95 int _ = ; > 96 END > 97 CASE(5) > 98 int X_[] = ; > 99 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 100 int _ = ; > 101 END > 102 */ > 103 } > 104 // END CUT HERE
Added SRM/616-U/1B-U.cpp version [8332f318b3fab8a0]
> 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 LongLongTripDiv1 { public: > 23 string isAble(int N, vector <int> A, vector <int> B, vector <int> D, lon > 24 { > 25 return solve(N, A, B, D, T) ? "Possible" : "Impossible"; > 26 } > 27 > 28 bool solve(int N, const vector <int>& A, const vector <int>& B, const ve > 29 { > 30 vector<vector<pair<int,int>>> edges(N); > 31 for(int i=0; i<A.size(); ++i) { > 32 edges[A[i]].emplace_back(B[i], D[i]); > 33 edges[B[i]].emplace_back(A[i], D[i]); > 34 } > 35 > 36 > 37 if(!solve_mod(99961, N, edges, T)) > 38 return false; > 39 if(!solve_mod(99971, N, edges, T)) > 40 return false; > 41 if(!solve_mod(99989, N, edges, T)) > 42 return false; > 43 if(!solve_mod(99991, N, edges, T)) > 44 return false; > 45 for(int mod=2; mod<=1000; ++mod) > 46 if(!solve_mod(mod, N, edges, T)) > 47 return false; > 48 return true; > 49 } > 50 > 51 bool solve_mod(int mod, int N, const vector<vector<pair<int,int>>>& E, l > 52 { > 53 vector<bool> V(mod*N); V[0*mod+0] = true; > 54 queue<int> Q; Q.push(0*mod+0); > 55 while(!Q.empty()) > 56 { > 57 int v = Q.front() / mod; > 58 int m = Q.front() % mod; > 59 Q.pop(); > 60 for(auto ud : E[v]) { > 61 int u = ud.first; > 62 int d = ud.second; > 63 int m2 = (m+d)%mod; > 64 if(!V[u*mod+m2]) { > 65 V[u*mod+m2] = true; > 66 Q.push(u*mod+m2); > 67 } > 68 } > 69 } > 70 return V[(N-1)*mod+int(T%mod)]; > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const string& Expected, const string& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, LongLongTripDiv1().isAble(N, A, B, D, T));} > 88 int main(){ > 89 > 90 CASE(6) > 91 int N = 50; > 92 int A_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, > 93 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 94 int B_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, > 95 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 96 int D_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 97 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 98 long long T = 1000000000000000000LL; > 99 string _ = "Possible"; > 100 END > 101 CASE(0) > 102 int N = 3; > 103 int A_[] = {0,0,1}; > 104 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 105 int B_[] = {2,1,2}; > 106 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 107 int D_[] = {7,6,5}; > 108 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 109 long long T = 11LL; > 110 string _ = "Possible"; > 111 END > 112 CASE(1) > 113 int N = 3; > 114 int A_[] = {0,0,1}; > 115 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 116 int B_[] = {2,1,2}; > 117 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 118 int D_[] = {7,6,5}; > 119 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 120 long long T = 25LL; > 121 string _ = "Possible"; > 122 END > 123 CASE(2) > 124 int N = 2; > 125 int A_[] = {0}; > 126 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 127 int B_[] = {1}; > 128 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 129 int D_[] = {1}; > 130 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 131 long long T = 9LL; > 132 string _ = "Possible"; > 133 END > 134 CASE(3) > 135 int N = 2; > 136 int A_[] = {1}; > 137 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 138 int B_[] = {0}; > 139 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 140 int D_[] = {1}; > 141 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 142 long long T = 1000000000000000000LL; > 143 string _ = "Impossible"; > 144 END > 145 CASE(4) > 146 int N = 4; > 147 int A_[] = {0,0,1}; > 148 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 149 int B_[] = {2,1,2}; > 150 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 151 int D_[] = {10,10,10}; > 152 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 153 long long T = 1000LL; > 154 string _ = "Impossible"; > 155 END > 156 CASE(5) > 157 int N = 9; > 158 int A_[] = {4,8,5,8,3,6,2,6,7,6,6}; > 159 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 160 int B_[] = {2,7,1,5,1,3,1,1,5,4,2}; > 161 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 162 int D_[] = {6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195}; > 163 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 164 long long T = 937186357646035002LL; > 165 string _ = "Impossible"; > 166 END > 167 } > 168 // END CUT HERE
Added SRM/616-U/1C.cpp version [2dc990563f003d05]
> 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 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned 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+=y; } > 33 > 34 class AlternativePiles { public: > 35 int count(string C, int M) > 36 { > 37 vector<mint> dp((M+1)*M); > 38 dp[0] = 1; > 39 > 40 for(char c : C) > 41 { > 42 vector<mint> dp2((M+1)*M); > 43 for(int m=0; m<=M; ++m) > 44 for(int r=0; r<M; ++r) { > 45 int mr = m*M+r; > 46 if((c=='R' || c=='W') && m+1<=M) > 47 dp2[(m+1)*M+(r+1)%M] += dp[mr]; > 48 if((c=='G' || c=='W') && m-1>=0) > 49 dp2[(m-1)*M+r] += dp[mr]; > 50 if(c=='B' || c=='W') > 51 dp2[m*M+r] += dp[mr]; > 52 } > 53 dp.swap(dp2); > 54 } > 55 return dp[0].val; > 56 } > 57 }; > 58 > 59 // BEGIN CUT HERE > 60 #include <ctime> > 61 double start_time; string timer() > 62 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 63 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 64 { os << "{ "; > 65 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 66 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 67 void verify_case(const int& Expected, const int& Received) { > 68 bool ok = (Expected == Received); > 69 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 70 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 71 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 72 #define END verify_case(_, AlternativePiles().count(C, M));} > 73 int main(){ > 74 > 75 CASE(0) > 76 string C = "WRGWWRGW"; > 77 int M = 2; > 78 int _ = 3; > 79 END > 80 CASE(1) > 81 string C = "RRGG"; > 82 int M = 1; > 83 int _ = 0; > 84 END > 85 CASE(2) > 86 string C = "BBBB"; > 87 int M = 5; > 88 int _ = 1; > 89 END > 90 CASE(3) > 91 string C = "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW > 92 int M = 50; > 93 int _ = 265470435; > 94 END > 95 CASE(4) > 96 string C = "WRWRGWWGWWWRWBWRWGWWRWBWWRGWBWGRGWWGWGRWGRWBRWBW"; > 97 int M = 7; > 98 int _ = 7400348; > 99 END > 100 /* > 101 CASE(6) > 102 string C = ; > 103 int M = ; > 104 int _ = ; > 105 END > 106 */ > 107 } > 108 // END CUT HERE