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

Added SRM/632-U/1A.cpp version [716106b188541b81]

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

Added SRM/632-U/1B-U.cpp version [2e1145b0d110a2f1]

            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  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           38  +
           39  +class CandyCupRunningCompetition { public:
           40  + int findMaximum(int N, vector <int> A, vector <int> B)
           41  + {
           42  +  const int START = 0, GOAL = N-1;
           43  +  typedef mint Flow;
           44  +  typedef int FlowFlag;
           45  +
           46  +  vector<vector<FlowFlag>> FF(N, vector<FlowFlag>(N, 0));
           47  +  vector<vector<Flow>> F(N, vector<Flow>(N, 0));
           48  +  vector<vector<int>> G(N);
           49  +  for(int i=0; i<A.size(); ++i) {
           50  +   int a = A[i], b = B[i];
           51  +   FF[a][b] = FF[b][a] = i+1;
           52  +   F[a][b] = F[b][a] = POW(3, i);
           53  +   G[a].push_back(b);
           54  +   G[b].push_back(a);
           55  +  }
           56  +
           57  +  Flow total = 0;
           58  +  for(;;) {
           59  +   // BFS
           60  +   vector<int> prev(N, -1);
           61  +   queue<int> q;
           62  +   prev[START] = START;
           63  +   q.push(START);
           64  +
           65  +   while(!q.empty()) {
           66  +    int u = q.front(); q.pop();
           67  +    for(int v: G[u]) if(prev[v]==-1 && FF[u][v]) {
           68  +     q.push(v);
           69  +     prev[v] = u;
           70  +     if(v == GOAL)
           71  +      goto endBfs;
           72  +    }
           73  +   }
           74  +  endBfs:
           75  +   if(prev[GOAL] == -1)
           76  +    break; // no more flow
           77  +
           78  +   Flow f;
           79  +   FlowFlag ff = 0x7fffffff;
           80  +   for(int v=GOAL; v!=prev[v]; v=prev[v]) {
           81  +    int u = prev[v];
           82  +    if(FF[u][v] < ff) {
           83  +     ff = FF[u][v];
           84  +     f = F[u][v];
           85  +    }
           86  +   }
           87  +
           88  +   total += f;
           89  +   for(int v=GOAL; v!=prev[v]; v=prev[v]) {
           90  +    int u = prev[v];
           91  +    F[u][v] -= f;
           92  +    F[v][u] += f;
           93  +    if(FF[u][v] == ff) {
           94  +     FF[u][v] = 0;
           95  +     FF[v][u] = ff;
           96  +    }
           97  +   }
           98  +  }
           99  +  return total.val;
          100  + }
          101  +};
          102  +
          103  +// BEGIN CUT HERE
          104  +#include <ctime>
          105  +double start_time; string timer()
          106  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          107  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          108  + { os << "{ ";
          109  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          110  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          111  +void verify_case(const int& Expected, const int& Received) {
          112  + bool ok = (Expected == Received);
          113  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          114  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          115  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          116  +#define END  verify_case(_, CandyCupRunningCompetition().findMaximum(N, A, B));}
          117  +int main(){
          118  +CASE(0)
          119  + int N = 3;
          120  + int A_[] = {0,1};
          121  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          122  + int B_[] = {1,2};
          123  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          124  + int _ = 1;
          125  +END
          126  +CASE(1)
          127  + int N = 4;
          128  + int A_[] = {0,1,0,2};
          129  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          130  + int B_[] = {1,3,2,3};
          131  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          132  + int _ = 10;
          133  +END
          134  +CASE(2)
          135  + int N = 3;
          136  + int A_[] = {0};
          137  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          138  + int B_[] = {1};
          139  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          140  + int _ = 0;
          141  +END
          142  +CASE(3)
          143  + int N = 5;
          144  + vector <int> A;
          145  + vector <int> B;
          146  + int _ = 0;
          147  +END
          148  +CASE(4)
          149  + int N = 6;
          150  + int A_[] = {1,1,2,0,4,3,0,1,4};
          151  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          152  + int B_[] = {3,2,3,1,5,5,2,4,3};
          153  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          154  + int _ = 39;
          155  +END
          156  +/*
          157  +CASE(5)
          158  + int N = ;
          159  + int A_[] = ;
          160  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          161  + int B_[] = ;
          162  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          163  + int _ = ;
          164  +END
          165  +CASE(6)
          166  + int N = ;
          167  + int A_[] = ;
          168  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          169  + int B_[] = ;
          170  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          171  + int _ = ;
          172  +END
          173  +*/
          174  +}
          175  +// END CUT HERE

Added SRM/632-U/1C-U.cpp version [5157fbd0866d284e]

            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  +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  +class PatternLock { public:
           39  + int solve(int N, int MOD)
           40  + {
           41  +  MODVAL = MOD;
           42  +  memo.resize(N+1, vector<int>(N+1, -1));
           43  +  return (rec(N,N)*2) % MOD;
           44  + }
           45  +
           46  + vector<vector<int>> memo;
           47  + int rec(int A, int B)
           48  + {
           49  +  if(memo[A][B] != -1)
           50  +   return memo[A][B];
           51  +  mint total;
           52  +  for(int a=0; a<A; ++a)
           53  +   total += rec(A, B, a);
           54  +  return memo[A][B] = total.val;
           55  + }
           56  + int rec(int A, int B, int a)
           57  + {
           58  +  if(A==1 && B==0)
           59  +   return 1;
           60  +
           61  +  mint total;
           62  +  if(B) total += rec(B, A-1);
           63  +  if(a>0) total += rec(A-1, B, a-1);
           64  +  if(a!=A-1) total += rec(A-1, B, a);
           65  +  return total.val;
           66  + }
           67  +};
           68  +
           69  +// BEGIN CUT HERE
           70  +#include <ctime>
           71  +double start_time; string timer()
           72  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           73  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           74  + { os << "{ ";
           75  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           76  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           77  +void verify_case(const int& Expected, const int& Received) {
           78  + bool ok = (Expected == Received);
           79  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           80  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           81  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           82  +#define END  verify_case(_, PatternLock().solve(N, MOD));}
           83  +int main(){
           84  +/*
           85  +CASE(0)
           86  + int N = 1;
           87  + int MOD = 12345667;
           88  + int _ = 2;
           89  +END
           90  +*/
           91  +CASE(1)
           92  + int N = 2;
           93  + int MOD = 324124124;
           94  + int _ = 24;
           95  +END
           96  +CASE(2)
           97  + int N = 3;
           98  + int MOD = 5325352;
           99  + int _ = 504;
          100  +END
          101  +CASE(3)
          102  + int N = 500;
          103  + int MOD = 1000000007;
          104  + int _ = 286169049;
          105  +END
          106  +/*
          107  +CASE(4)
          108  + int N = ;
          109  + int MOD = ;
          110  + int _ = ;
          111  +END
          112  +CASE(5)
          113  + int N = ;
          114  + int MOD = ;
          115  + int _ = ;
          116  +END
          117  +*/
          118  +}
          119  +// END CUT HERE