ADDED SRM/TCO21-2A-U/1A.cpp Index: SRM/TCO21-2A-U/1A.cpp ================================================================== --- SRM/TCO21-2A-U/1A.cpp +++ SRM/TCO21-2A-U/1A.cpp @@ -0,0 +1,83 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class RPSMagicTrick { public: + string guess(string exampleGuess, string exampleResponse, string volunteersActions) + { + string W = string() + exampleGuess[0]; + string L = string() + exampleGuess[1]; + bool T = (exampleResponse[0] == 'R'); + string ans; + for (int i = 0; i < volunteersActions.size(); ++i) { + if (volunteersActions[i] == '?') { + ans += (T ? W + L : L + W); + } + else { + T = !T; + } + } + return ans; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const string& Expected, const string& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, RPSMagicTrick().guess(exampleGuess, exampleResponse, volunteersActions));} +int main(){ +CASE(0) + string exampleGuess = "BA"; + string exampleResponse = "Right."; + string volunteersActions = "W?S??W??SS??WS?W??"; + string _ = "ABBAACBCCAABABABBACB"; +END +CASE(1) + string exampleGuess = "BA"; + string exampleResponse = "Wrong."; + string volunteersActions = "?S?WS?SW?WSWWS-???S??WWW?"; + string _ = "ABCBCBBACBBACBCBABCA"; +END +/* +CASE(2) + string exampleGuess = ; + string exampleResponse = ; + string volunteersActions = ; + string _ = ; +END +CASE(3) + string exampleGuess = ; + string exampleResponse = ; + string volunteersActions = ; + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO21-2A-U/1B.cpp Index: SRM/TCO21-2A-U/1B.cpp ================================================================== --- SRM/TCO21-2A-U/1B.cpp +++ SRM/TCO21-2A-U/1B.cpp @@ -0,0 +1,206 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class TheUltimatePackages { public: + vector count(int N, int D, vector Xprefix, vector Yprefix, int L, int seed) + { + vector X(D), Y(D); + int XL = Xprefix.size(); + + for (int i = 0; i maxdep(N, -1); + for (int i = 0; i < D; ++i) + maxdep[X[i]] = max(maxdep[X[i]], Y[i]); + + vector deped_by_all_larger; + int cur = N - 1; + for (int v = N - 1; v >= 0; --v) { + if (v == cur) + deped_by_all_larger.push_back(v); + if (maxdep[v] < cur) + cur = maxdep[v]; + } + + vector mindep(N, N); + for (int i = 0; i < D; ++i) + mindep[Y[i]] = min(mindep[Y[i]], X[i]); + + set deped_by_all_smaller; + cur = 0; + for (int v = 0; v <= N-1; ++v) { + if (v == cur) + deped_by_all_smaller.insert(v); + if (cur < mindep[v]) + cur = mindep[v]; + } + + int sum = 0; + int cnt = 0; + for (int v : deped_by_all_larger) + if (deped_by_all_smaller.count(v)) { + sum += v; + cnt += 1; + } + + vector ans = { cnt, sum }; + return ans; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, TheUltimatePackages().count(N, D, Xprefix, Yprefix, L, seed));} +int main(){ + +CASE(0) + int N = 5; + int D = 4; + int Xprefix_[] = {1, 3, 2, 4}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {0, 2, 1, 3}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 1; + int seed = 47; + int __[] = {5, 10 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int N = 5; + int D = 6; + int Xprefix_[] = {1, 2, 3, 4, 4, 4}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {0, 0, 0, 1, 3, 2}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 1; + int seed = 64; + int __[] = {2, 4 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int N = 5; + int D = 4; + int Xprefix_[] = {2, 2, 3, 4}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {0, 1, 2, 2}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 1; + int seed = 32532; + int __[] = {1, 2 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + int N = 4; + int D = 3; + int Xprefix_[] = {3, 3, 2}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {0, 2, 1}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 1; + int seed = 2555; + int __[] = {1, 3 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + int N = 7; + int D = 0; + vector Xprefix; + vector Yprefix; + int L = 1; + int seed = 0; + int __[] = {0, 0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int N = 2; + int D = 4; + int Xprefix_[] = {1, 1, 1, 1}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {0, 0, 0, 0}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 1; + int seed = 0; + int __[] = {2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + int N = 7; + int D = 12; + int Xprefix_[] = {2, 3, 4}; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = {1, 2, 3}; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = 5; + int seed = 4747; + int __[] = {0, 0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(7) + int N = ; + int D = ; + int Xprefix_[] = ; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = ; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = ; + int seed = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(8) + int N = ; + int D = ; + int Xprefix_[] = ; + vector Xprefix(Xprefix_, Xprefix_+sizeof(Xprefix_)/sizeof(*Xprefix_)); + int Yprefix_[] = ; + vector Yprefix(Yprefix_, Yprefix_+sizeof(Yprefix_)/sizeof(*Yprefix_)); + int L = ; + int seed = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE