Overview
| SHA1 Hash: | cda9cb77446a8fa82a5443a0b7b5d5cacd1afcfd |
|---|---|
| Date: | 2013-08-27 10:13:14 |
| User: | kinaba |
| Comment: | 587 |
| 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/587-U/1A.cpp version [806ffff6ad427e2d]
> 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 JumpFurther { public: > 23 int furthest(int N, int badStep) > 24 { > 25 int sigma = 0; > 26 for(int X=1; X<=N; ++X) > 27 { > 28 sigma += X; > 29 if(sigma == badStep) > 30 --sigma; > 31 } > 32 return sigma; > 33 } > 34 }; > 35 > 36 // BEGIN CUT HERE > 37 #include <ctime> > 38 double start_time; string timer() > 39 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 40 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 41 { os << "{ "; > 42 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 43 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 44 void verify_case(const int& Expected, const int& Received) { > 45 bool ok = (Expected == Received); > 46 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 47 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 48 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 49 #define END verify_case(_, JumpFurther().furthest(N, badStep));} > 50 int main(){ > 51 > 52 CASE(0) > 53 int N = 2; > 54 int badStep = 2; > 55 int _ = 3; > 56 END > 57 CASE(1) > 58 int N = 2; > 59 int badStep = 1; > 60 int _ = 2; > 61 END > 62 CASE(2) > 63 int N = 3; > 64 int badStep = 3; > 65 int _ = 5; > 66 END > 67 CASE(3) > 68 int N = 1313; > 69 int badStep = 5858; > 70 int _ = 862641; > 71 END > 72 CASE(4) > 73 int N = 1; > 74 int badStep = 757065; > 75 int _ = 1; > 76 END > 77 CASE(5) > 78 int N = 2000; > 79 int badStep = 123456; > 80 int _ = -1; > 81 END > 82 CASE(6) > 83 int N = 2000; > 84 int badStep = 3; > 85 int _ = -1; > 86 END > 87 CASE(7) > 88 int N = 2000; > 89 int badStep = 4000000; > 90 int _ = -1; > 91 END > 92 > 93 } > 94 // END CUT HERE
Added SRM/587-U/1B-U.cpp version [76ef41649a381040]
> 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 ThreeColorability { public: > 23 vector <string> lexSmallest(vector <string> cells) > 24 { > 25 if(!can(cells)) > 26 return vector<string>(); > 27 > 28 for(int y=0; y<cells.size(); ++y) > 29 for(int x=0; x<cells[y].size(); ++x) > 30 if(cells[y][x] == '?') > 31 { > 32 cells[y][x] = 'N'; > 33 if(!can(cells)) > 34 cells[y][x] = 'Z'; > 35 } > 36 return cells; > 37 } > 38 > 39 enum {R,G,B}; > 40 enum {RG,RB,GR,GB,BR,BG}; > 41 bool can(const vector<string>& C) > 42 { > 43 int N = C[0].size(); > 44 vector<int> P(N, (1<<6)-1); > 45 > 46 for(int y=0; y<C.size(); ++y) { > 47 apply(P, C[y]); > 48 > 49 int can = (1<<R)|(1<<G)|(1<<B); > 50 for(int x=0; x<N; ++x) > 51 { > 52 int can2 = 0; > 53 if((can&(1<<R))&&(P[x]&(1<<RG))) can2 |= 1<<G; > 54 if((can&(1<<R))&&(P[x]&(1<<RB))) can2 |= 1<<B; > 55 if((can&(1<<G))&&(P[x]&(1<<GR))) can2 |= 1<<R; > 56 if((can&(1<<G))&&(P[x]&(1<<GB))) can2 |= 1<<B; > 57 if((can&(1<<B))&&(P[x]&(1<<BR))) can2 |= 1<<R; > 58 if((can&(1<<B))&&(P[x]&(1<<BG))) can2 |= 1<<G; > 59 can = can2; > 60 } > 61 if(!can) > 62 return false; > 63 } > 64 > 65 return true; > 66 } > 67 > 68 void apply(vector<int>& P, const string& C) > 69 { > 70 for(int i=0; i<C.size(); ++i) > 71 apply(P[i], C[i]); > 72 } > 73 > 74 void apply(int& P, char C) > 75 { > 76 int Q = 0; > 77 // N > 78 if((P&(1<<RG))&&(C!='Z')) Q |= (1<<GB); > 79 if((P&(1<<RB))&&(C!='Z')) Q |= (1<<BG); > 80 if((P&(1<<GR))&&(C!='Z')) Q |= (1<<RB); > 81 if((P&(1<<GB))&&(C!='Z')) Q |= (1<<BR); > 82 if((P&(1<<BR))&&(C!='Z')) Q |= (1<<RG); > 83 if((P&(1<<BG))&&(C!='Z')) Q |= (1<<GR); > 84 // Z > 85 if((P&(1<<RG))&&(C!='N')) Q |= (1<<BR); > 86 if((P&(1<<RB))&&(C!='N')) Q |= (1<<GR); > 87 if((P&(1<<GR))&&(C!='N')) Q |= (1<<BG); > 88 if((P&(1<<GB))&&(C!='N')) Q |= (1<<RG); > 89 if((P&(1<<BR))&&(C!='N')) Q |= (1<<GB); > 90 if((P&(1<<BG))&&(C!='N')) Q |= (1<<RB); > 91 > 92 P = Q; > 93 } > 94 }; > 95 > 96 // BEGIN CUT HERE > 97 #include <ctime> > 98 double start_time; string timer() > 99 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 100 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 101 { os << "{ "; > 102 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 103 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 104 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 105 bool ok = (Expected == Received); > 106 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 107 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 108 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 109 #define END verify_case(_, ThreeColorability().lexSmallest(cells));} > 110 int main(){ > 111 > 112 CASE(0) > 113 string cells_[] = {"Z"}; > 114 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 115 string __[] = {"Z" }; > 116 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 CASE(1) > 119 string cells_[] = {"??", "?N"}; > 120 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 121 string __[] = {"NN", "NN" }; > 122 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 123 END > 124 CASE(2) > 125 string cells_[] = {"ZZZ", "ZNZ"}; > 126 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 127 vector <string> _; > 128 END > 129 CASE(3) > 130 string cells_[] = {"N?N??NN","??ZN??Z","NN???Z?","ZZZ?Z??","Z???NN?","N? > 131 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 132 vector <string> _; > 133 END > 134 CASE(4) > 135 string cells_[] = {"ZZZZ","ZZZZ","ZZZZ"}; > 136 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 137 string __[] = {"ZZZZ", "ZZZZ", "ZZZZ" }; > 138 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 139 END > 140 /* > 141 CASE(5) > 142 string cells_[] = ; > 143 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 144 string __[] = ; > 145 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 146 END > 147 CASE(6) > 148 string cells_[] = ; > 149 vector <string> cells(cells_, cells_+sizeof(cells_)/sizeof(*cells_)); > 150 string __[] = ; > 151 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 152 END > 153 */ > 154 } > 155 // END CUT HERE