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 volunteersActions) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 52 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 53 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 54 +#define END verify_case(_, RPSMagicTrick().guess(exampleGuess, exampleResponse, volunteersActions));} 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> Yprefix, int L, int seed) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 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, Yprefix, L, seed));} 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(*Xprefix_)); 102 + int Yprefix_[] = {0, 2, 1, 3}; 103 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 114 + int Yprefix_[] = {0, 0, 0, 1, 3, 2}; 115 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 126 + int Yprefix_[] = {0, 1, 2, 2}; 127 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 138 + int Yprefix_[] = {0, 2, 1}; 139 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 160 + int Yprefix_[] = {0, 0, 0, 0}; 161 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 172 + int Yprefix_[] = {1, 2, 3}; 173 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 185 + int Yprefix_[] = ; 186 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 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(*Xprefix_)); 197 + int Yprefix_[] = ; 198 + vector <int> Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); 199 + int L = ; 200 + int seed = ; 201 + int __[] = ; 202 + vector <int> _(__, __+sizeof(__)/sizeof(*__)); 203 +END 204 +*/ 205 +} 206 +// END CUT HERE