Overview
| SHA1 Hash: | e62379df86b4f330b962804c2096f272c2399cfa |
|---|---|
| Date: | 2021-05-22 17:40:48 |
| User: | kinaba |
| Comment: | TCO21 R2A |
| 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/TCO21-2A-U/1A.cpp version [b2dac1aad2e2f1af]
> 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 RPSMagicTrick { public: > 23 string guess(string exampleGuess, string exampleResponse, string volunte > 24 { > 25 string W = string() + exampleGuess[0]; > 26 string L = string() + exampleGuess[1]; > 27 bool T = (exampleResponse[0] == 'R'); > 28 string ans; > 29 for (int i = 0; i < volunteersActions.size(); ++i) { > 30 if (volunteersActions[i] == '?') { > 31 ans += (T ? W + L : L + W); > 32 } > 33 else { > 34 T = !T; > 35 } > 36 } > 37 return ans; > 38 } > 39 }; > 40 > 41 // BEGIN CUT HERE > 42 #include <ctime> > 43 double start_time; string timer() > 44 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 45 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 46 { os << "{ "; > 47 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 48 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 49 void verify_case(const string& Expected, const string& Received) { > 50 bool ok = (Expected == Received); > 51 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 52 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 53 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 54 #define END verify_case(_, RPSMagicTrick().guess(exampleGuess, exampleRespo > 55 int main(){ > 56 CASE(0) > 57 string exampleGuess = "BA"; > 58 string exampleResponse = "Right."; > 59 string volunteersActions = "W?S??W??SS??WS?W??"; > 60 string _ = "ABBAACBCCAABABABBACB"; > 61 END > 62 CASE(1) > 63 string exampleGuess = "BA"; > 64 string exampleResponse = "Wrong."; > 65 string volunteersActions = "?S?WS?SW?WSWWS-???S??WWW?"; > 66 string _ = "ABCBCBBACBBACBCBABCA"; > 67 END > 68 /* > 69 CASE(2) > 70 string exampleGuess = ; > 71 string exampleResponse = ; > 72 string volunteersActions = ; > 73 string _ = ; > 74 END > 75 CASE(3) > 76 string exampleGuess = ; > 77 string exampleResponse = ; > 78 string volunteersActions = ; > 79 string _ = ; > 80 END > 81 */ > 82 } > 83 // END CUT HERE
Added SRM/TCO21-2A-U/1B.cpp version [2941affd3a3de067]
> 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 TheUltimatePackages { public: > 23 vector <int> count(int N, int D, vector <int> Xprefix, vector <int> Ypre > 24 { > 25 vector<int> X(D), Y(D); > 26 int XL = Xprefix.size(); > 27 > 28 for (int i = 0; i<XL; ++i) { > 29 X[i] = Xprefix[i]; > 30 Y[i] = Yprefix[i]; > 31 } > 32 > 33 long long state = seed; > 34 for (int i = XL; i<D; ++i) { > 35 state = (state * 1103515245 + 12345) % (1LL << 31); > 36 int elen = 1 + state%L; > 37 state = (state * 1103515245 + 12345) % (1LL << 31); > 38 Y[i] = state % (N - elen); > 39 X[i] = Y[i] + elen; > 40 } > 41 > 42 vector<int> maxdep(N, -1); > 43 for (int i = 0; i < D; ++i) > 44 maxdep[X[i]] = max(maxdep[X[i]], Y[i]); > 45 > 46 vector<int> deped_by_all_larger; > 47 int cur = N - 1; > 48 for (int v = N - 1; v >= 0; --v) { > 49 if (v == cur) > 50 deped_by_all_larger.push_back(v); > 51 if (maxdep[v] < cur) > 52 cur = maxdep[v]; > 53 } > 54 > 55 vector<int> mindep(N, N); > 56 for (int i = 0; i < D; ++i) > 57 mindep[Y[i]] = min(mindep[Y[i]], X[i]); > 58 > 59 set<int> deped_by_all_smaller; > 60 cur = 0; > 61 for (int v = 0; v <= N-1; ++v) { > 62 if (v == cur) > 63 deped_by_all_smaller.insert(v); > 64 if (cur < mindep[v]) > 65 cur = mindep[v]; > 66 } > 67 > 68 int sum = 0; > 69 int cnt = 0; > 70 for (int v : deped_by_all_larger) > 71 if (deped_by_all_smaller.count(v)) { > 72 sum += v; > 73 cnt += 1; > 74 } > 75 > 76 vector<int> ans = { cnt, sum }; > 77 return ans; > 78 } > 79 }; > 80 > 81 // BEGIN CUT HERE > 82 #include <ctime> > 83 double start_time; string timer() > 84 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 85 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 86 { os << "{ "; > 87 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 88 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 89 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 90 bool ok = (Expected == Received); > 91 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 92 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 93 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 94 #define END verify_case(_, TheUltimatePackages().count(N, D, Xprefix, Ypref > 95 int main(){ > 96 > 97 CASE(0) > 98 int N = 5; > 99 int D = 4; > 100 int Xprefix_[] = {1, 3, 2, 4}; > 101 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 102 int Yprefix_[] = {0, 2, 1, 3}; > 103 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 104 int L = 1; > 105 int seed = 47; > 106 int __[] = {5, 10 }; > 107 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 108 END > 109 CASE(1) > 110 int N = 5; > 111 int D = 6; > 112 int Xprefix_[] = {1, 2, 3, 4, 4, 4}; > 113 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 114 int Yprefix_[] = {0, 0, 0, 1, 3, 2}; > 115 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 116 int L = 1; > 117 int seed = 64; > 118 int __[] = {2, 4 }; > 119 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 120 END > 121 CASE(2) > 122 int N = 5; > 123 int D = 4; > 124 int Xprefix_[] = {2, 2, 3, 4}; > 125 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 126 int Yprefix_[] = {0, 1, 2, 2}; > 127 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 128 int L = 1; > 129 int seed = 32532; > 130 int __[] = {1, 2 }; > 131 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 132 END > 133 CASE(3) > 134 int N = 4; > 135 int D = 3; > 136 int Xprefix_[] = {3, 3, 2}; > 137 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 138 int Yprefix_[] = {0, 2, 1}; > 139 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 140 int L = 1; > 141 int seed = 2555; > 142 int __[] = {1, 3 }; > 143 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 144 END > 145 CASE(4) > 146 int N = 7; > 147 int D = 0; > 148 vector <int> Xprefix; > 149 vector <int> Yprefix; > 150 int L = 1; > 151 int seed = 0; > 152 int __[] = {0, 0 }; > 153 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 154 END > 155 CASE(5) > 156 int N = 2; > 157 int D = 4; > 158 int Xprefix_[] = {1, 1, 1, 1}; > 159 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 160 int Yprefix_[] = {0, 0, 0, 0}; > 161 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 162 int L = 1; > 163 int seed = 0; > 164 int __[] = {2, 1 }; > 165 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 166 END > 167 CASE(6) > 168 int N = 7; > 169 int D = 12; > 170 int Xprefix_[] = {2, 3, 4}; > 171 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 172 int Yprefix_[] = {1, 2, 3}; > 173 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 174 int L = 5; > 175 int seed = 4747; > 176 int __[] = {0, 0 }; > 177 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 178 END > 179 /* > 180 CASE(7) > 181 int N = ; > 182 int D = ; > 183 int Xprefix_[] = ; > 184 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 185 int Yprefix_[] = ; > 186 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 187 int L = ; > 188 int seed = ; > 189 int __[] = ; > 190 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 191 END > 192 CASE(8) > 193 int N = ; > 194 int D = ; > 195 int Xprefix_[] = ; > 196 vector <int> Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xpref > 197 int Yprefix_[] = ; > 198 vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Ypref > 199 int L = ; > 200 int seed = ; > 201 int __[] = ; > 202 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 203 END > 204 */ > 205 } > 206 // END CUT HERE