Overview
| SHA1 Hash: | e6ccb20270c15cf05f8418a75b6591f0dbff2080 |
|---|---|
| Date: | 2014-05-17 14:41:20 |
| User: | kinaba |
| Comment: | 620 |
| 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/620-U/1A-U.cpp version [7aa46e2b547e667e]
> 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 PairGame { public: > 23 int maxSum(int a, int b, int c, int d) > 24 { > 25 vector<pair<int,int>> s1 = seq(a,b); > 26 vector<pair<int,int>> s2 = seq(c,d); > 27 int cand = -1; > 28 for(auto& p1: s1) > 29 for(auto& p2: s2) > 30 if(p1 == p2) > 31 cand = max(cand, p1.first + p1.second); > 32 return cand; > 33 } > 34 > 35 vector<pair<int,int>> seq(int a, int b) > 36 { > 37 vector<pair<int,int>> s; > 38 do { > 39 s.emplace_back(a, b); > 40 if(a<b) > 41 b-=a; > 42 else > 43 a-=b; > 44 } while(a && b); > 45 return s; > 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(_, PairGame().maxSum(a, b, c, d));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int a = 1; > 67 int b = 2; > 68 int c = 2; > 69 int d = 1; > 70 int _ = 2; > 71 END > 72 CASE(1) > 73 int a = 15; > 74 int b = 4; > 75 int c = 10; > 76 int d = 7; > 77 int _ = 7; > 78 END > 79 CASE(2) > 80 int a = 1; > 81 int b = 1; > 82 int c = 10; > 83 int d = 10; > 84 int _ = -1; > 85 END > 86 CASE(3) > 87 int a = 1000; > 88 int b = 1001; > 89 int c = 2000; > 90 int d = 2001; > 91 int _ = 1001; > 92 END > 93 CASE(4) > 94 int a = 10944; > 95 int b = 17928; > 96 int c = 7704; > 97 int d = 21888; > 98 int _ = 144; > 99 END > 100 CASE(5) > 101 int a = 1; > 102 int b = 1; > 103 int c = 1; > 104 int d = 1; > 105 int _ = 2; > 106 END > 107 /* > 108 CASE(6) > 109 int a = ; > 110 int b = ; > 111 int c = ; > 112 int d = ; > 113 int _ = ; > 114 END > 115 CASE(7) > 116 int a = ; > 117 int b = ; > 118 int c = ; > 119 int d = ; > 120 int _ = ; > 121 END > 122 */ > 123 } > 124 // END CUT HERE
Added SRM/620-U/1B.cpp version [111eb02783edc759]
> 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 CandidatesSelection { public: > 23 string possible(vector <string> score, vector <int> result) > 24 { > 25 return solve(score, result) ? "Possible" : "Impossible"; > 26 } > 27 > 28 bool solve(vector <string> score, vector <int> result) > 29 { > 30 const int N = score.size(); > 31 const int S = score[0].size(); > 32 > 33 // po[a][b] : bitmask of skill set that makes a<b. > 34 vector<vector<LL>> po(N, vector<LL>(N)); > 35 for(int a=0; a<N; ++a) > 36 for(int b=0; b<N; ++b) if(a!=b) > 37 { > 38 LL mask = 0; > 39 for(int s=0; s<S; ++s) > 40 if(score[a][s] <= score[b][s]) > 41 mask |= 1LL<<s; > 42 if(a<b) > 43 mask |= 1LL<<S; > 44 po[a][b] = mask; > 45 } > 46 > 47 vector<vector<int>> now(1, result); > 48 > 49 function<bool(LL,vector<vector<int>>)> rec; > 50 rec = [&](LL used, vector<vector<int>> obl) { > 51 LL pos = ~0LL; > 52 for(auto& oi: obl) > 53 for(int i=0; i+1<oi.size(); ++i) > 54 pos &= po[oi[i]][oi[i+1]]; > 55 if(pos & (1LL<<S)) // original order is enough. > 56 return true; > 57 > 58 bool changed = false; > 59 for(int s=0; s<S; ++s) if(pos & ~used & (1LL<<s)) { > 60 vector<vector<int>> next; > 61 for(auto& oi: obl) { > 62 vector<int> cur; > 63 for(int o: oi) { > 64 if(!cur.empty() && score[cur.bac > 65 changed = true; > 66 if(cur.size()>=2) > 67 next.push_back(c > 68 cur.clear(); > 69 } > 70 cur.push_back(o); > 71 } > 72 if(cur.size()>=2) > 73 next.push_back(cur); > 74 } > 75 obl = std::move(next); > 76 } > 77 return changed && rec(used|pos, obl); > 78 }; > 79 return rec(0, now); > 80 } > 81 > 82 }; > 83 > 84 // BEGIN CUT HERE > 85 #include <ctime> > 86 double start_time; string timer() > 87 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 88 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 89 { os << "{ "; > 90 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 91 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 92 void verify_case(const string& Expected, const string& Received) { > 93 bool ok = (Expected == Received); > 94 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 95 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 96 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 97 #define END verify_case(_, CandidatesSelection().possible(score, result));} > 98 int main(){ > 99 > 100 CASE(0) > 101 string score_[] = {"CC", "AA", "BB"}; > 102 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 103 int result_[] = {1,2,0}; > 104 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 105 string _ = "Possible"; > 106 END > 107 CASE(1) > 108 string score_[] = {"BAB", "ABB", "AAB", "ABA"}; > 109 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 110 int result_[] = {2,0,1,3}; > 111 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 112 string _ = "Possible"; > 113 END > 114 CASE(2) > 115 string score_[] = {"BAB", "ABB", "AAB", "ABA"}; > 116 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 117 int result_[] = {0, 1, 3, 2}; > 118 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 119 string _ = "Impossible"; > 120 END > 121 CASE(3) > 122 string score_[] = {"AAA", "ZZZ"}; > 123 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 124 int result_[] = {1, 0}; > 125 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 126 string _ = "Impossible"; > 127 END > 128 CASE(4) > 129 string score_[] = {"ZZZ", "AAA"}; > 130 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 131 int result_[] = {0, 1}; > 132 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 133 string _ = "Possible"; > 134 END > 135 CASE(5) > 136 string score_[] = {"ZYYYYX","YXZYXY","ZZZZXX","XZXYYX","ZZZYYZ","ZZXXYZ" > 137 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 138 int result_[] = {3,7,1,0,2,5,6,4}; > 139 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 140 string _ = "Possible"; > 141 END > 142 /* > 143 CASE(6) > 144 string score_[] = ; > 145 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 146 int result_[] = ; > 147 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 148 string _ = ; > 149 END > 150 CASE(7) > 151 string score_[] = ; > 152 vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_)); > 153 int result_[] = ; > 154 vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_)) > 155 string _ = ; > 156 END > 157 */ > 158 } > 159 // END CUT HERE