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

Added SRM/576-U/1A.cpp version [8b5e78cefb5c79ec]

            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 ArcadeManao { public:
           23  + int shortestLadder(vector <string> level, int coinRow, int coinColumn)
           24  + {
           25  +  for(int L=0; L<=level.size(); ++L)
           26  +   if(can(level, coinRow-1, coinColumn-1, L))
           27  +    return L;
           28  +  return level.size();
           29  + }
           30  +
           31  + bool can(vector <string> level, int Cy, int Cx, int L)
           32  + {
           33  +  int H = level.size();
           34  +  int W = level[0].size();
           35  +  typedef pair<int,int> point;
           36  +  set<point> V;
           37  +  queue<point> Q;
           38  +  Q.push(point(H-1, 0));
           39  +  V.insert(Q.front());
           40  +  while(!Q.empty()) {
           41  +   point p = Q.front();
           42  +   int y=p.first, x=p.second;
           43  +   Q.pop();
           44  +   if(y==Cy && x==Cx)
           45  +    return true;
           46  +   vector<point> cand;
           47  +   cand.push_back(point(y,x-1));
           48  +   cand.push_back(point(y,x+1));
           49  +   for(int dy=-L; dy<=+L; ++dy)
           50  +    cand.push_back(point(y+dy, x));
           51  +
           52  +   for(int i=0; i<cand.size(); ++i) {
           53  +    int yy = cand[i].first;
           54  +    int xx = cand[i].second;
           55  +    point pp(yy,xx);
           56  +    if(0<=yy&&yy<H&&0<=xx&&xx<W&&level[y][x]=='X'&&!V.count(pp)) {
           57  +     Q.push(pp);
           58  +     V.insert(pp);
           59  +    }
           60  +   }
           61  +  }
           62  +  return false;
           63  + }
           64  +};
           65  +
           66  +// BEGIN CUT HERE
           67  +#include <ctime>
           68  +double start_time; string timer()
           69  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           70  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           71  + { os << "{ ";
           72  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           73  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           74  +void verify_case(const int& Expected, const int& Received) {
           75  + bool ok = (Expected == Received);
           76  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           77  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           78  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           79  +#define END  verify_case(_, ArcadeManao().shortestLadder(level, coinRow, coinColumn));}
           80  +int main(){
           81  +
           82  +CASE(0)
           83  + string level_[] = {"XXXX....",
           84  + "...X.XXX",
           85  + "XXX..X..",
           86  + "......X.",
           87  + "XXXXXXXX"};
           88  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
           89  + int coinRow = 2;
           90  + int coinColumn = 4;
           91  + int _ = 2;
           92  +END
           93  +CASE(1)
           94  + string level_[] = {"XXXX",
           95  + "...X",
           96  + "XXXX"};
           97  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
           98  + int coinRow = 1;
           99  + int coinColumn = 1;
          100  + int _ = 1;
          101  +END
          102  +CASE(2)
          103  + string level_[] = {"..X..",
          104  + ".X.X.",
          105  + "X...X",
          106  + ".X.X.",
          107  + "..X..",
          108  + "XXXXX"};
          109  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
          110  + int coinRow = 1;
          111  + int coinColumn = 3;
          112  + int _ = 4;
          113  +END
          114  +CASE(3)
          115  + string level_[] = {"X"};
          116  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
          117  + int coinRow = 1;
          118  + int coinColumn = 1;
          119  + int _ = 0;
          120  +END
          121  +CASE(4)
          122  + string level_[] = {"XXXXXXXXXX",
          123  + "...X......",
          124  + "XXX.......",
          125  + "X.....XXXX",
          126  + "..XXXXX..X",
          127  + ".........X",
          128  + ".........X",
          129  + "XXXXXXXXXX"};
          130  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
          131  + int coinRow = 1;
          132  + int coinColumn = 1;
          133  + int _ = 2;
          134  +END
          135  +CASE(5)
          136  + string level_[] = {
          137  +  "XXXXXXXXXXXXXXX",
          138  +  "..............X",
          139  +  "..............X",
          140  +  "..............X",
          141  +  "XXXXXXXXXXXXXXX",
          142  +};
          143  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
          144  + int coinRow = 1;
          145  + int coinColumn = 1;
          146  + int _ = 1;
          147  +END
          148  +/*
          149  +CASE(6)
          150  + string level_[] = ;
          151  +   vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_));
          152  + int coinRow = ;
          153  + int coinColumn = ;
          154  + int _ = ;
          155  +END
          156  +*/
          157  +}
          158  +// END CUT HERE

Added SRM/576-U/1B-U.cpp version [8dbea917ed98c3a1]

            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 = 1000000009;
           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  +template<typename T>
           39  +struct DP4x
           40  +{
           41  + int N1, N2, N3, N4;
           42  + vector<T> data;
           43  + DP4x(int, int N2, int N3, int N4, const T& t = T())
           44  +  : N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           45  + T& operator()(int i1, int i2, int i3, int i4)
           46  +  { i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
           47  + void swap(DP4x& rhs)
           48  +  { data.swap(rhs.data); }
           49  +};
           50  +
           51  +class TheExperiment { public:
           52  + int countPlacements(vector <string> intensity, int M, int L, int A, int B)
           53  + {
           54  +  string S = accumulate(intensity.begin(), intensity.end(), string());
           55  +  int N = S.size();
           56  +
           57  +  vector<int> range_L, range_R; // [L,R)
           58  +  {
           59  +   vector<int> PS(N+1, 0);
           60  +   for(int i=0; i<N; ++i)
           61  +    PS[i+1] = PS[i] + (S[i]-'0');
           62  +   for(int i=0; i<N; ++i)
           63  +   {
           64  +    int LL = PS[i]+A;
           65  +    int RR = PS[i]+B+1;
           66  +    range_L.push_back(lower_bound(PS.begin(), PS.end(), LL) - PS.begin());
           67  +    range_R.push_back(lower_bound(PS.begin(), PS.end(), RR) - PS.begin());
           68  +    //cerr<<i<<" ["<<range_L.back()<<"-"<<range_R.back()<<")"<<" "<<LL<<","<<RR<<endl;
           69  +   }
           70  +  }
           71  +
           72  +  DP4x<mint> dp(M+1, N+1, M, 2);
           73  +  dp(0, 0, 0, 0) = 1;
           74  +  for(int i=0; i<M; ++i)
           75  +  {
           76  +   // Clear
           77  +   for(int x=0; x<=N; ++x)
           78  +   for(int rank=0; rank<M; ++rank) {
           79  +   for(int hami=0; hami<2; ++hami) {
           80  +    if(dp(i,x,rank,hami).val)
           81  +    cerr<<i<<" "<<x<<" "<<rank<<" "<<hami<<" : "<< dp(i,x,rank,hami).val<<endl;
           82  +    dp(i+1, x, rank, hami) = 0;
           83  +   }
           84  +
           85  +   // DP
           86  +   for(int x=0; x<N; ++x)
           87  +   for(int rank=0; rank<=i; ++rank)
           88  +   for(int hami=0; hami<2; ++hami)
           89  +   {
           90  +    mint v = dp(i,x,rank,hami);
           91  +    if(v.val != 0)
           92  +     for(int y=range_L[x]; y<range_R[x]; ++y)
           93  +     {
           94  +      if(y-x < L) {
           95  +       if(hami) {
           96  +        for(int r=0; r<=rank; ++r)
           97  +         dp(i+1, y, a) += v;
           98  +       } else {
           99  +       }
          100  +      } else if(y-x == L) {
          101  +       if(hami)
          102  +        dp(i+1, y, i, 0) += v * (rank+1);
          103  +       else
          104  +        dp(i+1, y, i, 0) += v * (rank+1);
          105  +      } else {
          106  +       break;
          107  +      }
          108  +     }
          109  +   }
          110  +  }
          111  +  mint acc = 0;
          112  +  for(int rank=0; rank<M; ++rank)
          113  +   acc += dp(M, N, rank, 0);
          114  +  return acc.val;
          115  + }
          116  +};
          117  +
          118  +// BEGIN CUT HERE
          119  +#include <ctime>
          120  +double start_time; string timer()
          121  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          122  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          123  + { os << "{ ";
          124  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          125  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          126  +void verify_case(const int& Expected, const int& Received) {
          127  + bool ok = (Expected == Received);
          128  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          129  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          130  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          131  +#define END  verify_case(_, TheExperiment().countPlacements(intensity, M, L, A, B));}
          132  +int main(){
          133  +
          134  +CASE(0)
          135  + string intensity_[] = {"341156"};
          136  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          137  + int M = 3;
          138  + int L = 3;
          139  + int A = 6;
          140  + int B = 10;
          141  + int _ = 2;
          142  +END
          143  +CASE(1)
          144  + string intensity_[] = {"999112999"};
          145  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          146  + int M = 2;
          147  + int L = 4;
          148  + int A = 21;
          149  + int B = 30;
          150  + int _ = 2;
          151  +END
          152  +CASE(2)
          153  + string intensity_[] = {"111"};
          154  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          155  + int M = 2;
          156  + int L = 2;
          157  + int A = 2;
          158  + int B = 3;
          159  + int _ = 0;
          160  +END
          161  +CASE(3)
          162  + string intensity_[] = {"59059", "110", "1132230231"};
          163  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          164  + int M = 1;
          165  + int L = 5;
          166  + int A = 10;
          167  + int B = 20;
          168  + int _ = 6;
          169  +END
          170  +CASE(4)
          171  + string intensity_[] = {"111111111111111111111111", "111111111111111111111111111", "11111111111111111111111"};
          172  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          173  + int M = 12;
          174  + int L = 8;
          175  + int A = 4;
          176  + int B = 2700;
          177  + int _ = 418629948;
          178  +END
          179  +/*
          180  +CASE(5)
          181  + string intensity_[] = ;
          182  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          183  + int M = ;
          184  + int L = ;
          185  + int A = ;
          186  + int B = ;
          187  + int _ = ;
          188  +END
          189  +CASE(6)
          190  + string intensity_[] = ;
          191  +   vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_));
          192  + int M = ;
          193  + int L = ;
          194  + int A = ;
          195  + int B = ;
          196  + int _ = ;
          197  +END
          198  +*/
          199  +}
          200  +// END CUT HERE