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

Added SRM/652-U/1A.cpp version [7d9c4ca801a229b3]

            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 CountryGroupHard { public:
           23  + string solve(vector <int> a)
           24  + {
           25  +  return rec(0, a)==1 ? "Sufficient" : "Insufficient";
           26  + }
           27  +
           28  + map<int, int> memo;
           29  + int rec(int k, const vector<int>& a)
           30  + {
           31  +  if(k == a.size())
           32  +   return 1;
           33  +  if(memo.count(k))
           34  +   return memo[k];
           35  +
           36  +  int cnt = 0;
           37  +  for(int v=1; k+v<=int(a.size()); ++v) {
           38  +   set<int> s(a.begin()+k, a.begin()+k+v);
           39  +   s.erase(0);
           40  +   s.erase(v);
           41  +   if(s.empty())
           42  +    cnt += rec(k+v, a);
           43  +  }
           44  +  return memo[k] = (cnt>=2 ? 2 : cnt);
           45  + }
           46  +};
           47  +
           48  +// BEGIN CUT HERE
           49  +#include <ctime>
           50  +double start_time; string timer()
           51  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           52  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           53  + { os << "{ ";
           54  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           55  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           56  +void verify_case(const string& Expected, const string& Received) {
           57  + bool ok = (Expected == Received);
           58  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           59  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           60  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           61  +#define END  verify_case(_, CountryGroupHard().solve(a));}
           62  +int main(){
           63  +
           64  +CASE(0)
           65  + int a_[] = {0,2,3,0,0};
           66  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           67  + string _ = "Sufficient";
           68  +END
           69  +CASE(1)
           70  + int a_[] = {0,2,0};
           71  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           72  + string _ = "Insufficient";
           73  +END
           74  +CASE(2)
           75  + int a_[] = {0,3,0,0,3,0};
           76  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           77  + string _ = "Sufficient";
           78  +END
           79  +CASE(3)
           80  + int a_[] = {0,0,3,3,0,0};
           81  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           82  + string _ = "Insufficient";
           83  +END
           84  +CASE(4)
           85  + int a_[] = {2,2,0,2,2};
           86  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           87  + string _ = "Sufficient";
           88  +END
           89  +/*
           90  +CASE(5)
           91  + int a_[] = ;
           92  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           93  + string _ = ;
           94  +END
           95  +CASE(6)
           96  + int a_[] = ;
           97  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
           98  + string _ = ;
           99  +END
          100  +*/
          101  +}
          102  +// END CUT HERE

Added SRM/652-U/1B.cpp version [ffc08068b2a48f88]

            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 T>
           23  +class IdGen
           24  +{
           25  + map<T, int> v2id_;
           26  + vector<T>   id2v_;
           27  +public:
           28  + int v2id(const T& v) {
           29  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           30  +  return v2id_[v];
           31  + }
           32  + const T& id2v(int i) const { return id2v_[i]; }
           33  + int size() const { return id2v_.size(); }
           34  +};
           35  +
           36  +template<typename Vert=pair<int,int>, typename Flow=LL, int NV=2048>
           37  +class MaxFlow
           38  +{
           39  + IdGen<Vert> idgen;
           40  + vector<int> G[NV];
           41  + Flow F[NV][NV];
           42  +
           43  +public:
           44  + void addEdge( Vert s_, Vert t_, Flow f )
           45  + {
           46  +  const int s = idgen.v2id(s_), t = idgen.v2id(t_);
           47  +  G[s].push_back(t);
           48  +  G[t].push_back(s);
           49  +  F[s][t] = f;
           50  +  F[t][s] = 0;
           51  + }
           52  +
           53  + Flow calc( Vert s_, Vert t_ )
           54  + {
           55  +  const int S = idgen.v2id(s_), D = idgen.v2id(t_);
           56  +  for( Flow total=0 ;; ) {
           57  +   // Do BFS and compute the level for each node.
           58  +   int LV[NV] = {0};
           59  +   vector<int> Q(1, S);
           60  +   for(int lv=1; !Q.empty(); ++lv) {
           61  +    vector<int> Q2;
           62  +    for(size_t i=0; i!=Q.size(); ++i) {
           63  +     const vector<int>& ne = G[Q[i]];
           64  +     for(size_t j=0; j!=ne.size(); ++j)
           65  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           66  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           67  +    }
           68  +    Q.swap(Q2);
           69  +   }
           70  +
           71  +   // Destination is now unreachable. Done.
           72  +   if( !LV[D] )
           73  +    return total;
           74  +
           75  +   // Iterating DFS.
           76  +   bool blocked[NV] = {};
           77  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           78  +  }
           79  + }
           80  +
           81  +private:
           82  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           83  + {
           84  +  Flow flow_out = 0;
           85  +  for(size_t i=0; i!=G[v].size(); ++i) {
           86  +   int u = G[v][i];
           87  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           88  +    Flow f = min(flow_in-flow_out, F[v][u]);
           89  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           90  +     F[v][u]  -= f;
           91  +     F[u][v]  += f;
           92  +     flow_out += f;
           93  +     if( flow_in == flow_out ) return flow_out;
           94  +    }
           95  +   }
           96  +  }
           97  +  blocked[v] = (flow_out==0);
           98  +  return flow_out;
           99  + }
          100  +};
          101  +
          102  +class Singing { public:
          103  + int solve(int N, int low, int high, vector <int> pitch)
          104  + {
          105  +  map<pair<int,int>, int> edge;
          106  +  for(int i=0; i+1<pitch.size(); ++i) {
          107  +   int p0 = min(pitch[i], pitch[i+1]);
          108  +   int p1 = max(pitch[i], pitch[i+1]);
          109  +   if(p0 != p1)
          110  +    edge[make_pair(p0,p1)] ++;
          111  +  }
          112  +
          113  +  MaxFlow<>* mf = new MaxFlow<>;
          114  +  const LL INF = 0x3fffffff;
          115  +
          116  +  enum{BOB, LEFT, RIGHT, ALICE};
          117  +  pair<int,int> Bob(BOB,0);
          118  +  pair<int,int> Alice(ALICE,0);
          119  +  for(int v=1; v<=N; ++v) {
          120  +   if(v>high)
          121  +    mf->addEdge(Bob, make_pair(LEFT,v), INF);
          122  +   mf->addEdge(make_pair(LEFT,v), make_pair(RIGHT,v), INF);
          123  +   if(v<low)
          124  +    mf->addEdge(make_pair(RIGHT,v), Alice, INF);
          125  +  }
          126  +  for(auto e: edge) {
          127  +   int v = e.first.first;
          128  +   int u = e.first.second;
          129  +   int c = e.second;
          130  +   mf->addEdge(make_pair(RIGHT,v), make_pair(LEFT,u), c);
          131  +   mf->addEdge(make_pair(RIGHT,u), make_pair(LEFT,v), c);
          132  +  }
          133  +
          134  +  LL ans = mf->calc(Bob, Alice);
          135  +  delete mf;
          136  +  return int(ans);
          137  + }
          138  +};
          139  +
          140  +// BEGIN CUT HERE
          141  +#include <ctime>
          142  +double start_time; string timer()
          143  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          144  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          145  + { os << "{ ";
          146  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          147  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          148  +void verify_case(const int& Expected, const int& Received) {
          149  + bool ok = (Expected == Received);
          150  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          151  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          152  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          153  +#define END  verify_case(_, Singing().solve(N, low, high, pitch));}
          154  +int main(){
          155  +
          156  +CASE(0)
          157  + int N = 3;
          158  + int low = 2;
          159  + int high = 2;
          160  + int pitch_[] = {1,2,3,2,1,2};
          161  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          162  + int _ = 2;
          163  +END
          164  +CASE(1)
          165  + int N = 10;
          166  + int low = 3;
          167  + int high = 7;
          168  + int pitch_[] = {4,4,5,5,6,5,3,6};
          169  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          170  + int _ = 0;
          171  +END
          172  +CASE(2)
          173  + int N = 6;
          174  + int low = 2;
          175  + int high = 5;
          176  + int pitch_[] = {5,3,1,6,4,2};
          177  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          178  + int _ = 1;
          179  +END
          180  +CASE(3)
          181  + int N = 10;
          182  + int low = 4;
          183  + int high = 5;
          184  + int pitch_[] = {1,4,3,5,2,5,7,5,9};
          185  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          186  + int _ = 3;
          187  +END
          188  +CASE(4)
          189  + int N = 100;
          190  + int low = 20;
          191  + int high = 80;
          192  + int pitch_[] = {2,27,3,53,53,52,52,60,85,89,100,53,60,2,3,53,100,89,40,42,2,53,2,85};
          193  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          194  + int _ = 5;
          195  +END
          196  +/*
          197  +CASE(5)
          198  + int N = ;
          199  + int low = ;
          200  + int high = ;
          201  + int pitch_[] = ;
          202  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          203  + int _ = ;
          204  +END
          205  +CASE(6)
          206  + int N = ;
          207  + int low = ;
          208  + int high = ;
          209  + int pitch_[] = ;
          210  +   vector <int> pitch(pitch_, pitch_+sizeof(pitch_)/sizeof(*pitch_));
          211  + int _ = ;
          212  +END
          213  +*/
          214  +}
          215  +// END CUT HERE

Added SRM/652-U/1C-U.cpp version [f01284ac275c4ca0]

            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  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint():val(0){}
           27  + mint(int      x):val(x%MODVAL) {}
           28  + mint(unsigned x):val(x%MODVAL) {}
           29  + mint(LL       x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +
           38  +// nCk :: O(1) time, O(n^2) space.
           39  +vector< vector<mint> > CP_;
           40  +mint C(int n, int k) {
           41  + while( CP_.size() <= n ) {
           42  +  int nn = CP_.size();
           43  +  CP_.push_back(vector<mint>(nn+1,1));
           44  +  for(int kk=1; kk<nn; ++kk)
           45  +   CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
           46  + }
           47  + return k<0 || n<k ? 0 : CP_[n][k];
           48  +}
           49  +
           50  +typedef tuple<int,int,int> Vec;
           51  +inline int operator*(Vec v, Vec u) {
           52  + return get<0>(v)*get<0>(u) + get<1>(v)*get<1>(u) + get<2>(v)*get<2>(u);
           53  +}
           54  +
           55  +class RockPaperScissorsMagic { public:
           56  + int count(int W, int L, int T, vector <int> card)
           57  + {
           58  +  const int N0 = std::count(card.begin(), card.end(), 0);
           59  +  const int N1 = std::count(card.begin(), card.end(), 1);
           60  +  const int N2 = std::count(card.begin(), card.end(), 2);
           61  +
           62  +  mint ans = 0;
           63  +  for(int x1=0; x1<=N0; ++x1)
           64  +  for(int x2=0; x1+x2<=N0; ++x2)
           65  +  for(int y1=0; y1<=N1; ++y1)
           66  +  for(int y2=0; y1+y2<=N1; ++y2)
           67  +  for(int z1=0; z1<=N2; ++z1)
           68  +  for(int z2=0; z1+z2<=N2; ++z2) {
           69  +   int x3,y3,z3;
           70  +   Vec x(x1, x2, x3=N0-x1-x2);
           71  +   Vec y(y1, y2, y3=N1-y1-y2);
           72  +   Vec z(z1, z2, z3=N2-z1-z2);
           73  +   Vec TLW(T,L,W);
           74  +   Vec WTL(W,T,L);
           75  +   Vec LTW(L,T,W);
           76  +   if(TLW*x+WTL*y != TLW*y+WTL*x) continue;
           77  +   if(T!=L && x1-x2!=y1-y2) continue;
           78  +   if(W!=L && x1-x3!=y1-y3) continue;
           79  +   if(TLW*x+WTL*z != TLW*z+WTL*x) continue;
           80  +   if(T!=L && x1-x2!=z1-z2) continue;
           81  +   if(W!=L && x1-x3!=z1-z3) continue;
           82  +
           83  +   ans += C(N0, x1) * C(N0-x1, x2)
           84  +    * C(N1, y1) * C(N1-y1, y2)
           85  +    * C(N2, z1) * C(N2-z1, z2);
           86  +  }
           87  +  return ans.val;
           88  + }
           89  +};
           90  +
           91  +// BEGIN CUT HERE
           92  +#include <ctime>
           93  +double start_time; string timer()
           94  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           95  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           96  + { os << "{ ";
           97  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           98  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           99  +void verify_case(const int& Expected, const int& Received) {
          100  + bool ok = (Expected == Received);
          101  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          102  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          103  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          104  +#define END  verify_case(_, RockPaperScissorsMagic().count(win, lose, tie, card));}
          105  +int main(){
          106  +
          107  +CASE(0)
          108  + int win = 2;
          109  + int lose = 0;
          110  + int tie = 1;
          111  + int card_[] = {0,1,2};
          112  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          113  + int _ = 3;
          114  +END
          115  +CASE(1)
          116  + int win = 2;
          117  + int lose = 0;
          118  + int tie = 1;
          119  + int card_[] = {0,0,0};
          120  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          121  + int _ = 6;
          122  +END
          123  +CASE(2)
          124  + int win = 0;
          125  + int lose = 0;
          126  + int tie = 0;
          127  + int card_[] = {1,0,2,2,2,0};
          128  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          129  + int _ = 729;
          130  +END
          131  +CASE(3)
          132  + int win = 514;
          133  + int lose = 451;
          134  + int tie = 145;
          135  + int card_[] = {0,0,0,0,0,1,1,1,1,1,1,2,2,2};
          136  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          137  + int _ = 0;
          138  +END
          139  +CASE(4)
          140  + int win = 3;
          141  + int lose = 6;
          142  + int tie = 9;
          143  + int card_[] = {0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2};
          144  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          145  + int _ = 2336040;
          146  +END
          147  +CASE(5)
          148  + int win = 514;
          149  + int lose = 451;
          150  + int tie = 145;
          151  + int card_[] = {0,0,0,1,1,1,1,1,1,2,2,2,2,2,2};
          152  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          153  + int _ = 116100;
          154  +END
          155  +/*
          156  +CASE(6)
          157  + int win = ;
          158  + int lose = ;
          159  + int tie = ;
          160  + int card_[] = ;
          161  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          162  + int _ = ;
          163  +END
          164  +CASE(7)
          165  + int win = ;
          166  + int lose = ;
          167  + int tie = ;
          168  + int card_[] = ;
          169  +   vector <int> card(card_, card_+sizeof(card_)/sizeof(*card_));
          170  + int _ = ;
          171  +END
          172  +*/
          173  +}
          174  +// END CUT HERE