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

Added SRM/578-U/1A.cpp version [7755a8c9ae69e1f9]

            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  +vector<mint> FAC_(1,1);
           43  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           44  +
           45  +// nCk :: O(1) time, O(n^2) space.
           46  +vector< vector<mint> > CP_;
           47  +mint C(LL n, LL k) {
           48  + while( CP_.size() <= n ) {
           49  +  int nn = CP_.size();
           50  +  CP_.push_back(vector<mint>(nn+1,1));
           51  +  for(int kk=1; kk<nn; ++kk)
           52  +   CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
           53  + }
           54  + return k<0 || n<k ? 0 : CP_[n][k];
           55  +}
           56  +
           57  +struct UnionFind
           58  +{
           59  + vector<int> uf, sz;
           60  + int nc;
           61  +
           62  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           63  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           64  + int size()
           65  +  { return nc; }
           66  + int size(int a)
           67  +  { return sz[Find(a)]; }
           68  + int Find(int a)
           69  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           70  + bool Union(int a, int b)
           71  +  {
           72  +   a = Find(a);
           73  +   b = Find(b);
           74  +   if( a != b )
           75  +   {
           76  +    if( sz[a] >= sz[b] ) swap(a, b);
           77  +    uf[a] = b;
           78  +    sz[b] += sz[a];
           79  +    --nc;
           80  +   }
           81  +   return (a!=b);
           82  +  }
           83  +};
           84  +
           85  +class GooseInZooDivOne { public:
           86  + int count(vector <string> field, int dist)
           87  + {
           88  +  int H = field.size();
           89  +  int W = field[0].size();
           90  +  vector<pair<int,int> > b;
           91  +  for(int y=0; y<H; ++y)
           92  +  for(int x=0; x<W; ++x)
           93  +   if(field[y][x] == 'v')
           94  +    b.push_back(make_pair(y,x));
           95  +
           96  +  int N = b.size();
           97  +  UnionFind uf(N);
           98  +  for(int i=0; i<N; ++i)
           99  +  for(int k=i+1; k<N; ++k) {
          100  +   int y = b[i].first;
          101  +   int x = b[i].second;
          102  +   int Y = b[k].first;
          103  +   int X = b[k].second;
          104  +   if(abs(y-Y)+abs(x-X) <= dist)
          105  +    uf.Union(i, k);
          106  +  }
          107  +
          108  +  int num[2]={0,0};
          109  +  for(int i=0; i<N; ++i)
          110  +   if(uf.Find(i) == i)
          111  +    num[uf.size(i)%2] ++;
          112  +  return solve(num[0], num[1]).val;
          113  + }
          114  +
          115  + mint solve(int ev, int od)
          116  + {
          117  +  mint total = 0;
          118  +  for(int k=0; k<=od; k+=2)
          119  +   total += C(od, k);
          120  +  return POW(2, ev) * total - 1;
          121  + }
          122  +};
          123  +
          124  +// BEGIN CUT HERE
          125  +#include <ctime>
          126  +double start_time; string timer()
          127  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          128  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          129  + { os << "{ ";
          130  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          131  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          132  +void verify_case(const int& Expected, const int& Received) {
          133  + bool ok = (Expected == Received);
          134  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          135  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          136  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          137  +#define END  verify_case(_, GooseInZooDivOne().count(field, dist));}
          138  +int main(){
          139  +
          140  +CASE(0)
          141  + string field_[] = {"vvv"};
          142  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          143  + int dist = 0;
          144  + int _ = 3;
          145  +END
          146  +CASE(1)
          147  + string field_[] = {"."};
          148  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          149  + int dist = 100;
          150  + int _ = 0;
          151  +END
          152  +CASE(2)
          153  + string field_[] = {"vvv"};
          154  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          155  + int dist = 1;
          156  + int _ = 0;
          157  +END
          158  +CASE(3)
          159  + string field_[] = {"v.v..................v............................"
          160  +,".v......v..................v.....................v"
          161  +,"..v.....v....v.........v...............v......v..."
          162  +,".........vvv...vv.v.........v.v..................v"
          163  +,".....v..........v......v..v...v.......v..........."
          164  +,"...................vv...............v.v..v.v..v..."
          165  +,".v.vv.................v..............v............"
          166  +,"..vv.......v...vv.v............vv.....v.....v....."
          167  +,"....v..........v....v........v.......v.v.v........"
          168  +,".v.......v.............v.v..........vv......v....."
          169  +,"....v.v.......v........v.....v.................v.."
          170  +,"....v..v..v.v..............v.v.v....v..........v.."
          171  +,"..........v...v...................v..............v"
          172  +,"..v........v..........................v....v..v..."
          173  +,"....................v..v.........vv........v......"
          174  +,"..v......v...............................v.v......"
          175  +,"..v.v..............v........v...............vv.vv."
          176  +,"...vv......v...............v.v..............v....."
          177  +,"............................v..v.................v"
          178  +,".v.............v.......v.........................."
          179  +,"......v...v........................v.............."
          180  +,".........v.....v..............vv.................."
          181  +,"................v..v..v.........v....v.......v...."
          182  +,"........v.....v.............v......v.v............"
          183  +,"...........v....................v.v....v.v.v...v.."
          184  +,"...........v......................v...v..........."
          185  +,"..........vv...........v.v.....................v.."
          186  +,".....................v......v............v...v...."
          187  +,".....vv..........................vv.v.....v.v....."
          188  +,".vv.......v...............v.......v..v.....v......"
          189  +,"............v................v..........v....v...."
          190  +,"................vv...v............................"
          191  +,"................v...........v........v...v....v..."
          192  +,"..v...v...v.............v...v........v....v..v...."
          193  +,"......v..v.......v........v..v....vv.............."
          194  +,"...........v..........v........v.v................"
          195  +,"v.v......v................v....................v.."
          196  +,".v........v................................v......"
          197  +,"............................v...v.......v........."
          198  +,"........................vv.v..............v...vv.."
          199  +,".......................vv........v.............v.."
          200  +,"...v.............v.........................v......"
          201  +,"....v......vv...........................v........."
          202  +,"....vv....v................v...vv..............v.."
          203  +,".................................................."
          204  +,"vv........v...v..v.....v..v..................v...."
          205  +,".........v..............v.vv.v.............v......"
          206  +,".......v.....v......v...............v............."
          207  +,"..v..................v................v....v......"
          208  +,".....v.....v.....................v.v......v......."};
          209  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          210  + int dist = 3;
          211  + int _ = 898961330;
          212  +END
          213  +/*
          214  +CASE(4)
          215  + string field_[] = ;
          216  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          217  + int dist = ;
          218  + int _ = ;
          219  +END
          220  +CASE(5)
          221  + string field_[] = ;
          222  +   vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_));
          223  + int dist = ;
          224  + int _ = ;
          225  +END
          226  +*/
          227  +}
          228  +// END CUT HERE

Added SRM/578-U/1B-U.cpp version [65c638c38947b473]

            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  +
           24  +class WolfInZooDivOne { public:
           25  + int count(int N, vector <string> L_, vector <string> R_)
           26  + {
           27  +  vector<int> L, R;
           28  +  {
           29  +   stringstream sin(accumulate(L_.begin(), L_.end(), string()));
           30  +   for(int s; sin>>s;) L.push_back(s);
           31  +  }
           32  +  {
           33  +   stringstream sin(accumulate(R_.begin(), R_.end(), string()));
           34  +   for(int s; sin>>s;) R.push_back(s+1);
           35  +  }
           36  +
           37  +  set< pair<int,int> > LR;
           38  +  for(int i=0; i<L.size(); ++i)
           39  +   LR.insert(make_pair(L[i], R[i]));
           40  +
           41  +  vector< pair<int,int> > LR_imp;
           42  +  for(set< pair<int,int> >::iterator it=LR.begin(); it!=LR.end(); ++it) {
           43  +   bool important = true;
           44  +   for(set< pair<int,int> >::iterator kt=LR.begin(); kt!=LR.end(); ++kt)
           45  +    if(it != kt && kt->first<=it->first && it->second<=kt->second)
           46  +     important = false;
           47  +   if(important)
           48  +    LR_imp.push_back(*it);
           49  +  }
           50  +
           51  +  return solve(N, LR_imp);
           52  + }
           53  +
           54  + int solve(int N, const vector< pair<int,int> >& LR)
           55  + {
           56  +  memo = vector<vector<vector<int> > >(N,
           57  +   vector<vector<int> >(LR.size()+1, vector<int>(LR.size()+1, -1)));
           58  +  return rec(0, N, LR, 0, 0, 0, 0);
           59  + }
           60  +
           61  + vector<vector<vector<int> > > memo;
           62  + int rec(int i, const int N, const vector< pair<int,int> >& LR, int end_of_past, int end_of_two, int end_of_one,
           63  +  int end_of_zero)
           64  + {
           65  +  if(i == N)
           66  +   return 1;
           67  +  int& me = memo[i][end_of_two][end_of_one];
           68  +  if(me != -1)
           69  +   return me;
           70  +
           71  +  int ez = end_of_zero;
           72  +  while(ez<LR.size() && LR[ez].first<=i)
           73  +   ++ez;
           74  +  int ep = end_of_past;
           75  +  while(ep<ez && LR[ep].second<=i)
           76  +   ++ep;
           77  +
           78  +  // do not place wolf at i.
           79  +  int total = rec(i+1, N, LR, ep, max(ep,end_of_two), max(ep,end_of_one), ez);
           80  +
           81  +  // place wolf at i.
           82  +  if(ep >= end_of_two) {
           83  +   int e1 = max(ep, end_of_one);
           84  +   int e2 = max(ep, end_of_two);
           85  +   while(e2<e1 && i<LR[e2].second)
           86  +    ++e2;
           87  +   while(e1<ez && i<LR[e1].second)
           88  +    ++e1;
           89  +   total += rec(i+1, N, LR, ep, e2, e1, ez);
           90  +  }
           91  +  return me = (total % MODVAL);
           92  + }
           93  +};
           94  +
           95  +// BEGIN CUT HERE
           96  +#include <ctime>
           97  +double start_time; string timer()
           98  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           99  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          100  + { os << "{ ";
          101  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          102  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          103  +void verify_case(const int& Expected, const int& Received) {
          104  + bool ok = (Expected == Received);
          105  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          106  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          107  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          108  +#define END  verify_case(_, WolfInZooDivOne().count(N, L, R));}
          109  +int main(){
          110  +
          111  +CASE(0)
          112  + int N = 5;
          113  + string L_[] = {"0"};
          114  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          115  + string R_[] = {"4"};
          116  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          117  + int _ = 16;
          118  +END
          119  +CASE(1)
          120  + int N = 5;
          121  + string L_[] = {"0 1"};
          122  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          123  + string R_[] = {"2 4"};
          124  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          125  + int _ = 21;
          126  +END
          127  +CASE(2)
          128  + int N = 10;
          129  + string L_[] = {"0 4 2 7"};
          130  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          131  + string R_[] = {"3 9 5 9"};
          132  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          133  + int _ = 225;
          134  +END
          135  +CASE(3)
          136  + int N = 100;
          137  + string L_[] = {"0 2 2 7 10 1","3 16 22 30 33 38"," 42 44 49 51 57 60 62"," 65 69 72 74 77 7","8 81 84 88 91 93 96"};
          138  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          139  + string R_[] = {"41 5 13 22 12 13 ","33 41 80 47 40 ","4","8 96 57 66 ","80 60 71 79"," 70 77 ","99"," 83 85 93 88 89 97 97 98"};
          140  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          141  + int _ = 6419882;
          142  +END
          143  +/*
          144  +CASE(4)
          145  + int N = ;
          146  + string L_[] = ;
          147  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          148  + string R_[] = ;
          149  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          150  + int _ = ;
          151  +END
          152  +CASE(5)
          153  + int N = ;
          154  + string L_[] = ;
          155  +   vector <string> L(L_, L_+sizeof(L_)/sizeof(*L_));
          156  + string R_[] = ;
          157  +   vector <string> R(R_, R_+sizeof(R_)/sizeof(*R_));
          158  + int _ = ;
          159  +END
          160  +*/
          161  +}
          162  +// END CUT HERE