• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/TCO17-2C-U/1A.cpp version [a42c7d53ea89e664]

            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 CanidsSeesaw { public:
           23  + vector <int> construct(vector <int> wolf, vector <int> fox, int k)
           24  + {
           25  +  partial_sum(wolf.begin(), wolf.end(), wolf.begin());
           26  +
           27  +  vector<pair<int, int>> fox_idx;
           28  +  for (int i = 0; i < fox.size(); ++i)
           29  +   fox_idx.emplace_back(fox[i], i);
           30  +
           31  +  sort(fox_idx.rbegin(), fox_idx.rend());
           32  +  while (point_of(fox_idx, wolf) > k) {
           33  +   bool swapped = false;
           34  +   for(int i=0; i+1<fox_idx.size(); ++i)
           35  +    if (fox_idx[i] > fox_idx[i + 1])
           36  +    {
           37  +     swap(fox_idx[i], fox_idx[i + 1]);
           38  +     swapped = true;
           39  +     break;
           40  +    }
           41  +   if (!swapped)break;
           42  +  }
           43  +
           44  +  if (point_of(fox_idx, wolf) == k) {
           45  +   vector<int> idx;
           46  +   for (auto fi : fox_idx)
           47  +    idx.push_back(fi.second);
           48  +   return idx;
           49  +  }
           50  +  return vector<int>();
           51  + }
           52  +
           53  + int point_of(const vector<pair<int,int>>& fox_idx, const vector<int>& wolf_sum) {
           54  +  int score = 0, cur = 0;
           55  +  for (int i = 0; i < fox_idx.size(); ++i) {
           56  +   cur += fox_idx[i].first;
           57  +   if (cur > wolf_sum[i])
           58  +    ++score;
           59  +  }
           60  +  return score;
           61  + }
           62  +};
           63  +
           64  +// BEGIN CUT HERE
           65  +#include <ctime>
           66  +double start_time; string timer()
           67  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           68  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           69  + { os << "{ ";
           70  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           71  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           72  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           73  + bool ok = (Expected == Received);
           74  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           75  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           76  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           77  +#define END  verify_case(_, CanidsSeesaw().construct(wolf, fox, k));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + int wolf_[] = {3,1};
           82  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
           83  + int fox_[] = {4,2};
           84  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
           85  + int k = 1;
           86  + int __[] = {1, 0 };
           87  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           88  +END
           89  +CASE(1)
           90  + int wolf_[] = {1,3};
           91  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
           92  + int fox_[] = {4,2};
           93  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
           94  + int k = 1;
           95  + vector <int> _;
           96  +END
           97  +CASE(2)
           98  + int wolf_[] = {10,10,10,10,10,10,10,10,10,10};
           99  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
          100  + int fox_[] = {1,100,1,100,1,100,1,100,1,100};
          101  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
          102  + int k = 7;
          103  + int __[] = {0, 2, 4, 1, 6, 3, 5, 7, 9, 8 };
          104  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          105  +END
          106  +CASE(3)
          107  + int wolf_[] = {10,10,10,10,10,10,10,10,10,10};
          108  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
          109  + int fox_[] = {1,100,1,100,1,100,1,100,1,100};
          110  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
          111  + int k = 4;
          112  + vector <int> _;
          113  +END
          114  +CASE(4)
          115  + int wolf_[] = {2};
          116  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
          117  + int fox_[] = {1};
          118  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
          119  + int k = 0;
          120  + int __[] = {0 };
          121  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          122  +END
          123  +/*
          124  +CASE(5)
          125  + int wolf_[] = ;
          126  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
          127  + int fox_[] = ;
          128  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
          129  + int k = ;
          130  + int __[] = ;
          131  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          132  +END
          133  +CASE(6)
          134  + int wolf_[] = ;
          135  +   vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_));
          136  + int fox_[] = ;
          137  +   vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_));
          138  + int k = ;
          139  + int __[] = ;
          140  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          141  +END
          142  +*/
          143  +}
          144  +// END CUT HERE

Added SRM/TCO17-2C-U/1B.cpp version [ce17f42a8e0e96e1]

            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  +template<typename Vert=int, typename Flow=int, int NV = 50>
           23  +class MaxFlow
           24  +{
           25  + vector<int> G[NV];
           26  + Flow F[NV][NV];
           27  +
           28  +public:
           29  + void addEdge(Vert s, Vert t)
           30  + {
           31  +  G[s].push_back(t);
           32  +  G[t].push_back(s);
           33  +  F[s][t] = 1;
           34  +  F[t][s] = 1;
           35  + }
           36  +
           37  + Flow calc(Vert S, Vert D)
           38  + {
           39  +  for (Flow total = 0;; ) {
           40  +   // Do BFS and compute the level for each node.
           41  +   int LV[NV] = { 0 };
           42  +   vector<int> Q(1, S);
           43  +   for (int lv = 1; !Q.empty(); ++lv) {
           44  +    vector<int> Q2;
           45  +    for (size_t i = 0; i != Q.size(); ++i) {
           46  +     const vector<int>& ne = G[Q[i]];
           47  +     for (size_t j = 0; j != ne.size(); ++j)
           48  +      if (F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j] != S)
           49  +       LV[ne[j]] = lv, Q2.push_back(ne[j]);
           50  +    }
           51  +    Q.swap(Q2);
           52  +   }
           53  +
           54  +   // Destination is now unreachable. Done.
           55  +   if (!LV[D])
           56  +    return total;
           57  +
           58  +   // Iterating DFS.
           59  +   bool blocked[NV] = {};
           60  +   total += dinic_dfs(S, D, LV, 0x7fffffff, blocked);
           61  +  }
           62  + }
           63  +
           64  +private:
           65  + Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[])
           66  + {
           67  +  Flow flow_out = 0;
           68  +  for (size_t i = 0; i != G[v].size(); ++i) {
           69  +   int u = G[v][i];
           70  +   if (LV[v] + 1 == LV[u] && F[v][u]) {
           71  +    Flow f = min(flow_in - flow_out, F[v][u]);
           72  +    if (u == D || !blocked[u] && (f = dinic_dfs(u, D, LV, f, blocked))>0) {
           73  +     F[v][u] -= f;
           74  +     F[u][v] += f;
           75  +     flow_out += f;
           76  +     if (flow_in == flow_out) return flow_out;
           77  +    }
           78  +   }
           79  +  }
           80  +  blocked[v] = (flow_out == 0);
           81  +  return flow_out;
           82  + }
           83  +};
           84  +
           85  +class AngelDemonGame { public:
           86  + string winner(vector <string> G, int A, int D)
           87  + {
           88  +  const int N = G.size();
           89  +  if (D >= N - 1)
           90  +   return "Demon"; // by cutting all the edges around 0.
           91  +
           92  +  // Since A>=2, there are at least (n-1) way
           93  +  //   0--(n-1) or 0--k--(n-1) for all k
           94  +  // possible and disjoint paths. Devil cannot prevent all of them.
           95  +  // If and only if Angle can make mincut > D, Angle certainly wins.
           96  +  // Otherwise Demon may luckily choose the mincut.
           97  +  return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown";
           98  + }
           99  +
          100  + bool canMakeMinCutLargerThanD(int N, vector<string> G, int A, int D)
          101  + {
          102  +  if (G[0][N - 1] == 'N') {
          103  +   G[0][N - 1] = G[N - 1][0] = 'Y';
          104  +   --A;
          105  +  }
          106  +
          107  +  set<int> Lchance, Rchance;
          108  +  for (int u = 1; u < N - 1; ++u) {
          109  +   if (G[0][u] == 'N') Lchance.insert(u);
          110  +   if (G[u][N-1] == 'N') Rchance.insert(u);
          111  +  }
          112  +
          113  +  int cur = minCut(N, G);
          114  +  while(cur <= D && A > 0) {
          115  +   for (int u : Lchance) {
          116  +    G[0][u] = G[u][0] = 'Y';
          117  +    if (minCut(N, G) > cur) {
          118  +     --A;
          119  +     ++cur;
          120  +     Lchance.erase(u);
          121  +     goto next;
          122  +    }
          123  +    G[0][u] = G[u][0] = 'N';
          124  +   }
          125  +   for (int u : Rchance) {
          126  +    G[u][N-1] = G[N-1][u] = 'Y';
          127  +    if (minCut(N, G) > cur) {
          128  +     --A;
          129  +     ++cur;
          130  +     Rchance.erase(u);
          131  +     goto next;
          132  +    }
          133  +    G[u][N - 1] = G[N - 1][u] = 'N';
          134  +   }
          135  +
          136  +   if (!Lchance.empty()) {
          137  +    int u = *Lchance.begin();
          138  +    G[0][u] = G[u][0] = 'Y';
          139  +    Lchance.erase(u);
          140  +    --A;
          141  +    goto next;
          142  +   }
          143  +   if (!Rchance.empty()) {
          144  +    int u = *Rchance.begin();
          145  +    G[0][u] = G[u][0] = 'Y';
          146  +    Rchance.erase(u);
          147  +    --A;
          148  +    goto next;
          149  +   }
          150  +  next:;
          151  +  }
          152  +
          153  +  return cur > D;
          154  + }
          155  +
          156  + int minCut(int N, const vector<string>& G)
          157  + {
          158  +  MaxFlow<> mf;
          159  +  for (int u = 0; u < N; ++u)
          160  +   for (int v = u + 1; v < N; ++v)
          161  +    if (G[u][v] == 'Y')
          162  +     mf.addEdge(u, v);
          163  +  return mf.calc(0, N - 1);
          164  + }
          165  +};
          166  +
          167  +// BEGIN CUT HERE
          168  +#include <ctime>
          169  +double start_time; string timer()
          170  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          171  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          172  + { os << "{ ";
          173  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          174  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          175  +void verify_case(const string& Expected, const string& Received) {
          176  + bool ok = (Expected == Received);
          177  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          178  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          179  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          180  +#define END  verify_case(_, AngelDemonGame().winner(G, A, D));}
          181  +int main(){
          182  +
          183  +CASE(0)
          184  + string G_[] = {"NYNY",
          185  + "YNYY",
          186  + "NYNN",
          187  + "YYNN"};
          188  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          189  + int A = 2;
          190  + int D = 2;
          191  + string _ = "Angel";
          192  +END
          193  +CASE(1)
          194  + string G_[] = {"NYNY",
          195  + "YNYY",
          196  + "NYNN",
          197  + "YYNN"};
          198  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          199  + int A = 6;
          200  + int D = 6;
          201  + string _ = "Demon";
          202  +END
          203  +CASE(2)
          204  + string G_[] = {"NNNN",
          205  + "NNNN",
          206  + "NNNN",
          207  + "NNNN"};
          208  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          209  + int A = 2;
          210  + int D = 2;
          211  + string _ = "Unknown";
          212  +END
          213  +CASE(3)
          214  + string G_[] = {"NYNNNY",
          215  + "YNNYNN",
          216  + "NNNNYN",
          217  + "NYNNNN",
          218  + "NNYNNN",
          219  + "YNNNNN"};
          220  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          221  + int A = 4;
          222  + int D = 4;
          223  + string _ = "Unknown";
          224  +END
          225  +CASE(4)
          226  + string G_[] = {"NYNNNY",
          227  + "YNNYNN",
          228  + "NNNNYN",
          229  + "NYNNNN",
          230  + "NNYNNN",
          231  + "YNNNNN"};
          232  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          233  + int A = 8;
          234  + int D = 4;
          235  + string _ = "Angel";
          236  +END
          237  +CASE(5)
          238  + string G_[] = {"NYNNNY",
          239  + "YNNYNN",
          240  + "NNNNYN",
          241  + "NYNNNN",
          242  + "NNYNNN",
          243  + "YNNNNN"};
          244  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          245  + int A = 4;
          246  + int D = 8;
          247  + string _ = "Demon";
          248  +END
          249  +CASE(6)
          250  + string G_[] = { "NNNN","NNNN","NNNN","NNNN" };
          251  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          252  + int A = 4;
          253  + int D = 2;
          254  + string _ = "Unknown";
          255  +END
          256  +/*
          257  +CASE(7)
          258  + string G_[] = ;
          259  +   vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
          260  + int A = ;
          261  + int D = ;
          262  + string _ = ;
          263  +END
          264  +*/
          265  +}
          266  +// END CUT HERE