Overview
| SHA1 Hash: | f3a2b0598891746160a3bbee6e53b82ea8297752 |
|---|---|
| Date: | 2013-10-15 11:24:16 |
| User: | kinaba |
| Comment: | 593 |
| 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/593-U/1A.cpp version [b9269837f6b290a6]
> 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 HexagonalBoard { public: > 23 typedef pair<int,int> vert; > 24 > 25 int minColors(vector <string> board) > 26 { > 27 int H = board.size(); > 28 int W = board[0].size(); > 29 > 30 map<vert, vector<vert>> G; > 31 > 32 bool has_edge = false; > 33 for(int y=0; y<H; ++y) > 34 for(int x=0; x<W; ++x) if(board[y][x]=='X') { > 35 G[vert(y,x)]; > 36 for(int Y=0; Y<H; ++Y) > 37 for(int X=0; X<W; ++X) if(board[Y][X]=='X') > 38 if(juxt(y,x,Y,X)) { > 39 has_edge = true; > 40 G[vert(y,x)].emplace_back(Y,X); > 41 } > 42 } > 43 > 44 if(G.empty()) > 45 return 0; > 46 if(!has_edge) > 47 return 1; > 48 return two(G) ? 2 : 3; > 49 } > 50 > 51 bool juxt(int y, int x, int Y, int X) > 52 { > 53 if(y==Y && x==X) > 54 return false; > 55 if(y==Y) > 56 return abs(x-X) == 1; > 57 if(y+1==Y) > 58 return x-1==X || x==X; > 59 if(Y+1==y) > 60 return X-1==x || X==x; > 61 return false; > 62 } > 63 > 64 bool two(map<vert, vector<vert>>& G) > 65 { > 66 map<vert, int> C; > 67 for(auto it=G.begin(); it!=G.end(); ++it) > 68 if(!C.count(it->first)) > 69 if(!rec(it->first, G, C, 0)) > 70 return false; > 71 return true; > 72 } > 73 > 74 bool rec(vert v, map<vert, vector<vert>>& G, map<vert,int>& C, int c) > 75 { > 76 if(C.count(v)) > 77 return C[v] == c; > 78 C[v] = c; > 79 auto& ne = G[v]; > 80 for(int i=0; i<ne.size(); ++i) > 81 if(!rec(ne[i], G, C, c^1)) > 82 return false; > 83 return true; > 84 } > 85 }; > 86 > 87 // BEGIN CUT HERE > 88 #include <ctime> > 89 double start_time; string timer() > 90 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 91 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 92 { os << "{ "; > 93 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 94 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 95 void verify_case(const int& Expected, const int& Received) { > 96 bool ok = (Expected == Received); > 97 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 98 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 99 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 100 #define END verify_case(_, HexagonalBoard().minColors(board));} > 101 int main(){ > 102 > 103 CASE(0) > 104 string board_[] = {"---", > 105 "---", > 106 "---"} > 107 ; > 108 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 109 int _ = 0; > 110 END > 111 CASE(1) > 112 string board_[] = {"-X--", > 113 "---X", > 114 "----", > 115 "-X--"}; > 116 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 117 int _ = 1; > 118 END > 119 CASE(2) > 120 string board_[] = {"XXXX", > 121 "---X", > 122 "---X", > 123 "---X"}; > 124 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 125 int _ = 2; > 126 END > 127 CASE(3) > 128 string board_[] = {"XX-XX--" > 129 ,"-XX-XXX" > 130 ,"X-XX--X" > 131 ,"X--X-X-" > 132 ,"XX-X-XX" > 133 ,"-X-XX-X" > 134 ,"-XX-XX-"}; > 135 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 136 int _ = 3; > 137 END > 138 /* > 139 CASE(4) > 140 string board_[] = ; > 141 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 142 int _ = ; > 143 END > 144 CASE(5) > 145 string board_[] = ; > 146 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 147 int _ = ; > 148 END > 149 */ > 150 } > 151 // END CUT HERE
Added SRM/593-U/1B.cpp version [a69937141079332f]
> 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 MayTheBestPetWin { public: > 23 int calc(vector <int> A, vector <int> B) > 24 { > 25 const int N = A.size(); > 26 vector<int> C(N); > 27 for(int i=0; i<N; ++i) > 28 C[i] = A[i] + B[i]; > 29 > 30 const int allmin = accumulate(A.begin(), A.end(), 0); > 31 const int allmax = accumulate(B.begin(), B.end(), 0); > 32 const int allsum = accumulate(C.begin(), C.end(), 0); > 33 > 34 vector<bool> can(allsum+1); > 35 can[0] = true; > 36 for(int i=0; i<N; ++i) > 37 for(int k=allsum; k>=C[i]; --k) > 38 if(can[k-C[i]]) > 39 can[k] = true; > 40 > 41 int best = allsum; > 42 for(int i=0; i<=allsum; ++i) > 43 if(can[i]) > 44 best = min(best, max(abs(i-allmin), abs(allmax-i > 45 return best; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, MayTheBestPetWin().calc(A, B));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int A_[] = {3,4,4,7}; > 67 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 68 int B_[] = {3,4,4,7}; > 69 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 70 int _ = 2; > 71 END > 72 CASE(1) > 73 int A_[] = {1,3,5,4,5}; > 74 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 75 int B_[] = {2,5,6,8,7}; > 76 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 77 int _ = 5; > 78 END > 79 CASE(2) > 80 int A_[] = {2907,949,1674,6092,8608,5186,2630,970,1050,2415,1923,2697,55 > 81 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 82 int B_[] = {7296,6954,4407,9724,8645,8065,9323,8433,1352,9618,6487,7309, > 83 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 84 int _ = 52873; > 85 END > 86 /* > 87 CASE(3) > 88 int A_[] = ; > 89 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 90 int B_[] = ; > 91 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 92 int _ = ; > 93 END > 94 CASE(4) > 95 int A_[] = ; > 96 vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); > 97 int B_[] = ; > 98 vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); > 99 int _ = ; > 100 END > 101 */ > 102 } > 103 // END CUT HERE