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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 47 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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) << " msec)"; return os.str(); } 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 os; } 104 +void verify_case(const vector <string>& Expected, const vector <string>& Received) { 105 + bool ok = (Expected == Received); 106 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 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?????N","ZZ?N?NN"}; 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