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

Added SRM/564-U/1A.cpp version [15bba962603caf18]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +struct UnionFind
           23  +{
           24  + vector<int> uf, sz;
           25  + int nc;
           26  +
           27  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           28  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           29  + int size()
           30  +  { return nc; }
           31  + int size(int a)
           32  +  { return sz[Find(a)]; }
           33  + int Find(int a)
           34  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           35  + bool Union(int a, int b)
           36  +  {
           37  +   a = Find(a);
           38  +   b = Find(b);
           39  +   if( a != b )
           40  +   {
           41  +    if( sz[a] >= sz[b] ) swap(a, b);
           42  +    uf[a] = b;
           43  +    sz[b] += sz[a];
           44  +    --nc;
           45  +   }
           46  +   return (a!=b);
           47  +  }
           48  +};
           49  +
           50  +class KnightCircuit2 { public:
           51  + int maxSize(int w, int h)
           52  + {
           53  +  if( w>=4 && h>=4 )
           54  +   return w*h;
           55  +
           56  +  UnionFind uf(w*h);
           57  +  int dy[] = {+2,+2,-2,-2,+1,+1,-1,-1};
           58  +  int dx[] = {+1,-1,+1,-1,+2,-2,+2,-2};
           59  +  for(int y=0; y<h; ++y)
           60  +  for(int x=0; x<w; ++x)
           61  +  for(int d=0; d<8; ++d) {
           62  +   int yy = y+dy[d];
           63  +   int xx = x+dx[d];
           64  +   if(0<=yy && yy<h && 0<=xx && xx<w)
           65  +    uf.Union(y*w+x, yy*w+xx);
           66  +  }
           67  +
           68  +  int m = 0;
           69  +  for(int i=0; i<w*h; ++i)
           70  +   m = max(m, uf.size(i));
           71  +  return m;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const int& Expected, const int& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, KnightCircuit2().maxSize(w, h));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int w = 1;
           93  + int h = 1;
           94  + int _ = 1;
           95  +END
           96  +CASE(1)
           97  + int w = 15;
           98  + int h = 2;
           99  + int _ = 8;
          100  +END
          101  +CASE(2)
          102  + int w = 100;
          103  + int h = 100;
          104  + int _ = 10000;
          105  +END
          106  +/*
          107  +CASE(3)
          108  + int w = ;
          109  + int h = ;
          110  + int _ = ;
          111  +END
          112  +CASE(4)
          113  + int w = ;
          114  + int h = ;
          115  + int _ = ;
          116  +END
          117  +*/
          118  +}
          119  +// END CUT HERE

Added SRM/564-U/1B.cpp version [fd5e5eb809d8d0f9]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class AlternateColors2 { public:
           23  + long long countWays(int n, int k)
           24  + {
           25  +  LL total = 0;
           26  +  for(int mini=0; mini*3<=n; ++mini)
           27  +  {
           28  +   if(mini*3 == n) {
           29  +    total += rgb(mini, mini, mini, k) ? 1 : 0;
           30  +   } else {
           31  +    total += rgb(mini, mini, n-mini*2, k) ? 1 : 0;
           32  +    total += rgb(mini, n-mini*2, mini, k) ? 1 : 0;
           33  +    total += rgb(n-mini*2, mini, mini, k) ? 1 : 0;
           34  +    int free = n - mini*3;
           35  +    if(free >= 2) {
           36  +     if(k <= mini*3) {
           37  +      if((k-1)%3==0) {
           38  +       total += (free - 1)*3;
           39  +      }
           40  +     } else {
           41  +      total += twoball(free, k-mini*3) * 2;
           42  +     }
           43  +    }
           44  +   }
           45  +  }
           46  +  return total;
           47  + }
           48  +
           49  + bool rgb(int r, int g, int b, int k) {
           50  +  int mini = min(r, min(g, b));
           51  +  if( k <= mini*3 )
           52  +   return (k-1)%3==0;
           53  +  r -= mini;
           54  +  g -= mini;
           55  +  b -= mini;
           56  +  k -= mini*3;
           57  +  if(r==0) return false;
           58  +  if(g==0) return xx(r,b,k);
           59  +  if(b==0) return xx(r,g,k);
           60  + }
           61  +
           62  + bool xx(int r, int g, int k)
           63  + {
           64  +  int mini = min(r,g);
           65  +  if( k <= mini*2 )
           66  +   return (k-1)%2 == 0;
           67  +  r -= mini;
           68  +  g -= mini;
           69  +  k -= mini*2;
           70  +  return r>0;
           71  + }
           72  +
           73  + LL twoball(int n, int k)
           74  + {
           75  +  int MM = (k-1)/2;
           76  +  LL total = MM;
           77  +  if( (MM+1)*2 <= n && (k-1)%2==0 )
           78  +   total += (n-(MM+1)*2 + 1);
           79  +  return total;
           80  + }
           81  +};
           82  +
           83  +// BEGIN CUT HERE
           84  +#include <ctime>
           85  +double start_time; string timer()
           86  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           87  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           88  + { os << "{ ";
           89  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           90  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           91  +void verify_case(const long long& Expected, const long long& Received) {
           92  + bool ok = (Expected == Received);
           93  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           94  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           95  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           96  +#define END  verify_case(_, AlternateColors2().countWays(n, k));}
           97  +int main(){
           98  +
           99  +CASE(0)
          100  + int n = 1;
          101  + int k = 1;
          102  + long long _ = 1LL;
          103  +END
          104  +CASE(1)
          105  + int n = 3;
          106  + int k = 3;
          107  + long long _ = 3LL;
          108  +END
          109  +CASE(2)
          110  + int n = 6;
          111  + int k = 4;
          112  + long long _ = 9LL;
          113  +END
          114  +CASE(3)
          115  + int n = 6;
          116  + int k = 1;
          117  + long long _ = 21LL;
          118  +END
          119  +CASE(4)
          120  + int n = 1000;
          121  + int k = 2;
          122  + long long _ = 1LL;
          123  +END
          124  +CASE(5)
          125  + int n = 100000;
          126  + int k = 100000;
          127  + long long _ = 1666700000LL;
          128  +END
          129  +CASE(6)
          130  + int n = 100000;
          131  + int k = 100;
          132  + long long _ = -1LL;
          133  +END
          134  +/*
          135  +CASE(7)
          136  + int n = ;
          137  + int k = ;
          138  + long long _ = LL;
          139  +END
          140  +*/
          141  +}
          142  +// END CUT HERE

Added SRM/564-U/1C-U.cpp version [e66651725115e70a]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> 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  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           39  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           40  +mint operator/(mint x, mint y) { return x/=y; }
           41  +
           42  +class DefectiveAddition { public:
           43  + int count(vector <int> cards, int n)
           44  + {
           45  +  int n_msb = 0;
           46  +  while( (1<<n_msb+1) <= n ) {}
           47  +
           48  +  vector<int> cc(30);
           49  +  vector<int> more;
           50  +  for(int i=0; i<cards.size(); ++i) {
           51  +   for(int k=0; k<=29; ++k)
           52  +   {
           53  +    if((1<<k)<=cards[i] && cards[i]<(1<<k+1))
           54  +     cc[k].push_back(cards[i]);
           55  +   }
           56  +  }
           57  +
           58  +  mint p = 0;
           59  +  for(int k=29; k>=0; --k)
           60  +  {
           61  +   int BIT = (n>>k)&1;
           62  +
           63  +   int up = 0;
           64  +
           65  +   vector<int> rel;
           66  +   for(int i=0; i<cards.size(); ++i)
           67  +    if( (1<<k) <= cards[i] ) {
           68  +     if( (1<<k+1) <= cards[i] )
           69  +      up ^= cards[i];
           70  +     if( (1<<k) & cards[i] )
           71  +      rel.push_back(i);
           72  +    }
           73  +
           74  +   // all take above
           75  +   if( (up>>k+1) == (n>>k+1) )
           76  +   {
           77  +    for(int ri=0; ri<rel.size(); ++ri)
           78  +    {
           79  +     int i = rel[ri];
           80  +    }
           81  +   }
           82  +  }
           83  +  return p.val;
           84  + }
           85  +};
           86  +
           87  +// BEGIN CUT HERE
           88  +#include <ctime>
           89  +double start_time; string timer()
           90  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           91  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           92  + { os << "{ ";
           93  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           94  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           95  +void verify_case(const int& Expected, const int& Received) {
           96  + bool ok = (Expected == Received);
           97  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           98  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           99  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          100  +#define END  verify_case(_, DefectiveAddition().count(cards, n));}
          101  +int main(){
          102  +
          103  +CASE(0)
          104  + int cards_[] = {2,3};
          105  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          106  + int n = 2;
          107  + int _ = 3;
          108  +END
          109  +CASE(1)
          110  + int cards_[] = {1,2,3};
          111  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          112  + int n = 1;
          113  + int _ = 6;
          114  +END
          115  +CASE(2)
          116  + int cards_[] = {4, 5, 7, 11};
          117  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          118  + int n = 6;
          119  + int _ = 240;
          120  +END
          121  +CASE(3)
          122  + int cards_[] = {1,2,3,4,5,6,7,8,9,10};
          123  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          124  + int n = 15;
          125  + int _ = 1965600;
          126  +END
          127  +CASE(4)
          128  + int cards_[] = {1,2,3,4,5,6,7,8,9,10};
          129  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          130  + int n = 16;
          131  + int _ = 0;
          132  +END
          133  +CASE(5)
          134  + int cards_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
          135  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          136  + int n = 1;
          137  + int _ = 949480669;
          138  +END
          139  +/*
          140  +CASE(6)
          141  + int cards_[] = ;
          142  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          143  + int n = ;
          144  + int _ = ;
          145  +END
          146  +CASE(7)
          147  + int cards_[] = ;
          148  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          149  + int n = ;
          150  + int _ = ;
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE