ADDED SRM/TCO17-2C-U/1A.cpp Index: SRM/TCO17-2C-U/1A.cpp ================================================================== --- SRM/TCO17-2C-U/1A.cpp +++ SRM/TCO17-2C-U/1A.cpp @@ -0,0 +1,144 @@ +#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 CanidsSeesaw { public: + vector construct(vector wolf, vector fox, int k) + { + partial_sum(wolf.begin(), wolf.end(), wolf.begin()); + + vector> fox_idx; + for (int i = 0; i < fox.size(); ++i) + fox_idx.emplace_back(fox[i], i); + + sort(fox_idx.rbegin(), fox_idx.rend()); + while (point_of(fox_idx, wolf) > k) { + bool swapped = false; + for(int i=0; i+1 fox_idx[i + 1]) + { + swap(fox_idx[i], fox_idx[i + 1]); + swapped = true; + break; + } + if (!swapped)break; + } + + if (point_of(fox_idx, wolf) == k) { + vector idx; + for (auto fi : fox_idx) + idx.push_back(fi.second); + return idx; + } + return vector(); + } + + int point_of(const vector>& fox_idx, const vector& wolf_sum) { + int score = 0, cur = 0; + for (int i = 0; i < fox_idx.size(); ++i) { + cur += fox_idx[i].first; + if (cur > wolf_sum[i]) + ++score; + } + return score; + } +}; + +// 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(_, CanidsSeesaw().construct(wolf, fox, k));} +int main(){ + +CASE(0) + int wolf_[] = {3,1}; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = {4,2}; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = 1; + int __[] = {1, 0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int wolf_[] = {1,3}; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = {4,2}; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = 1; + vector _; +END +CASE(2) + int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = {1,100,1,100,1,100,1,100,1,100}; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = 7; + int __[] = {0, 2, 4, 1, 6, 3, 5, 7, 9, 8 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = {1,100,1,100,1,100,1,100,1,100}; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = 4; + vector _; +END +CASE(4) + int wolf_[] = {2}; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = {1}; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = 0; + int __[] = {0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(5) + int wolf_[] = ; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = ; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + int wolf_[] = ; + vector wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); + int fox_[] = ; + vector fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); + int k = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE ADDED SRM/TCO17-2C-U/1B.cpp Index: SRM/TCO17-2C-U/1B.cpp ================================================================== --- SRM/TCO17-2C-U/1B.cpp +++ SRM/TCO17-2C-U/1B.cpp @@ -0,0 +1,266 @@ +#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; + +template +class MaxFlow +{ + vector G[NV]; + Flow F[NV][NV]; + +public: + void addEdge(Vert s, Vert t) + { + G[s].push_back(t); + G[t].push_back(s); + F[s][t] = 1; + F[t][s] = 1; + } + + Flow calc(Vert S, Vert D) + { + for (Flow total = 0;; ) { + // Do BFS and compute the level for each node. + int LV[NV] = { 0 }; + vector Q(1, S); + for (int lv = 1; !Q.empty(); ++lv) { + vector Q2; + for (size_t i = 0; i != Q.size(); ++i) { + const vector& ne = G[Q[i]]; + for (size_t j = 0; j != ne.size(); ++j) + if (F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j] != S) + LV[ne[j]] = lv, Q2.push_back(ne[j]); + } + Q.swap(Q2); + } + + // Destination is now unreachable. Done. + if (!LV[D]) + return total; + + // Iterating DFS. + bool blocked[NV] = {}; + total += dinic_dfs(S, D, LV, 0x7fffffff, blocked); + } + } + +private: + Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[]) + { + Flow flow_out = 0; + for (size_t i = 0; i != G[v].size(); ++i) { + int u = G[v][i]; + if (LV[v] + 1 == LV[u] && F[v][u]) { + Flow f = min(flow_in - flow_out, F[v][u]); + if (u == D || !blocked[u] && (f = dinic_dfs(u, D, LV, f, blocked))>0) { + F[v][u] -= f; + F[u][v] += f; + flow_out += f; + if (flow_in == flow_out) return flow_out; + } + } + } + blocked[v] = (flow_out == 0); + return flow_out; + } +}; + +class AngelDemonGame { public: + string winner(vector G, int A, int D) + { + const int N = G.size(); + if (D >= N - 1) + return "Demon"; // by cutting all the edges around 0. + + // Since A>=2, there are at least (n-1) way + // 0--(n-1) or 0--k--(n-1) for all k + // possible and disjoint paths. Devil cannot prevent all of them. + // If and only if Angle can make mincut > D, Angle certainly wins. + // Otherwise Demon may luckily choose the mincut. + return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown"; + } + + bool canMakeMinCutLargerThanD(int N, vector G, int A, int D) + { + if (G[0][N - 1] == 'N') { + G[0][N - 1] = G[N - 1][0] = 'Y'; + --A; + } + + set Lchance, Rchance; + for (int u = 1; u < N - 1; ++u) { + if (G[0][u] == 'N') Lchance.insert(u); + if (G[u][N-1] == 'N') Rchance.insert(u); + } + + int cur = minCut(N, G); + while(cur <= D && A > 0) { + for (int u : Lchance) { + G[0][u] = G[u][0] = 'Y'; + if (minCut(N, G) > cur) { + --A; + ++cur; + Lchance.erase(u); + goto next; + } + G[0][u] = G[u][0] = 'N'; + } + for (int u : Rchance) { + G[u][N-1] = G[N-1][u] = 'Y'; + if (minCut(N, G) > cur) { + --A; + ++cur; + Rchance.erase(u); + goto next; + } + G[u][N - 1] = G[N - 1][u] = 'N'; + } + + if (!Lchance.empty()) { + int u = *Lchance.begin(); + G[0][u] = G[u][0] = 'Y'; + Lchance.erase(u); + --A; + goto next; + } + if (!Rchance.empty()) { + int u = *Rchance.begin(); + G[0][u] = G[u][0] = 'Y'; + Rchance.erase(u); + --A; + goto next; + } + next:; + } + + return cur > D; + } + + int minCut(int N, const vector& G) + { + MaxFlow<> mf; + for (int u = 0; u < N; ++u) + for (int v = u + 1; v < N; ++v) + if (G[u][v] == 'Y') + mf.addEdge(u, v); + return mf.calc(0, N - 1); + } +}; + +// 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(_, AngelDemonGame().winner(G, A, D));} +int main(){ + +CASE(0) + string G_[] = {"NYNY", + "YNYY", + "NYNN", + "YYNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 2; + int D = 2; + string _ = "Angel"; +END +CASE(1) + string G_[] = {"NYNY", + "YNYY", + "NYNN", + "YYNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 6; + int D = 6; + string _ = "Demon"; +END +CASE(2) + string G_[] = {"NNNN", + "NNNN", + "NNNN", + "NNNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 2; + int D = 2; + string _ = "Unknown"; +END +CASE(3) + string G_[] = {"NYNNNY", + "YNNYNN", + "NNNNYN", + "NYNNNN", + "NNYNNN", + "YNNNNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 4; + int D = 4; + string _ = "Unknown"; +END +CASE(4) + string G_[] = {"NYNNNY", + "YNNYNN", + "NNNNYN", + "NYNNNN", + "NNYNNN", + "YNNNNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 8; + int D = 4; + string _ = "Angel"; +END +CASE(5) + string G_[] = {"NYNNNY", + "YNNYNN", + "NNNNYN", + "NYNNNN", + "NNYNNN", + "YNNNNN"}; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 4; + int D = 8; + string _ = "Demon"; +END +CASE(6) + string G_[] = { "NNNN","NNNN","NNNN","NNNN" }; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = 4; + int D = 2; + string _ = "Unknown"; +END +/* +CASE(7) + string G_[] = ; + vector G(G_, G_+sizeof(G_)/sizeof(*G_)); + int A = ; + int D = ; + string _ = ; +END +*/ +} +// END CUT HERE