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

Added SRM/TCO20-3B-U/1A.cpp version [56c161848bbee859]

            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 VisitALot { public:
           23  + string travel(int R, int C, vector <int> obsr, vector <int> obsc)
           24  + {
           25  +  if (R >= 6) {
           26  +   string ans;
           27  +   int r = 0, c = 0;
           28  +   while (r < R) {
           29  +    if (count(obsr.begin(), obsr.end(), r) == 0) {
           30  +     if (c == 0)
           31  +      while (c + 1 < C) {
           32  +       ans += 'E';
           33  +       c++;
           34  +      }
           35  +     else
           36  +      while (c - 1 >= 0) {
           37  +       ans += 'W';
           38  +       c--;
           39  +      }
           40  +    }
           41  +
           42  +    if (r + 1 < R)
           43  +     ans += 'S';
           44  +    r++;
           45  +   }
           46  +   return ans;
           47  +  }
           48  +
           49  +  if (C >= 6) {
           50  +   string ans;
           51  +   int r = 0, c = 0;
           52  +   while (c < C) {
           53  +    if (count(obsc.begin(), obsc.end(), c) == 0) {
           54  +     if (r == 0)
           55  +      while (r + 1 < R) {
           56  +       ans += 'S';
           57  +       r++;
           58  +      }
           59  +     else
           60  +      while (r - 1 >= 0) {
           61  +       ans += 'N';
           62  +       r--;
           63  +      }
           64  +    }
           65  +
           66  +    if (c + 1 < C)
           67  +     ans += 'E';
           68  +    c++;
           69  +   }
           70  +   return ans;
           71  +  }
           72  +
           73  +  // naive search
           74  +  vector<vector<bool>> visited(R, vector<bool>(C));
           75  +  for (int i = 0; i < obsr.size(); ++i)
           76  +   visited[obsr[i]][obsc[i]] = true;
           77  +  visited[0][0] = true;
           78  +  string ans;
           79  +  dfs(ans, R, C, 0, 0, visited);
           80  +  return ans;
           81  + }
           82  +
           83  + bool dfs(string& s, int R, int C, int r, int c, vector<vector<bool>>& visited) {
           84  +  int dr[] = { -1,+1,0,0 };
           85  +  int dc[] = { 0,0,-1,+1 };
           86  +  char dd[] = { 'N', 'S', 'W', 'E' };
           87  +  for (int i = 0; i < 4; ++i) {
           88  +   int rr = r + dr[i];
           89  +   int cc = c + dc[i];
           90  +   if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[rr][cc]) {
           91  +    visited[rr][cc] = true;
           92  +    s += dd[i];
           93  +    if (s.size()+1 >= (R*C+1)/2 || dfs(s, R, C, rr, cc, visited))
           94  +     return true;
           95  +    s.resize(s.size() - 1);
           96  +    visited[rr][cc] = false;
           97  +   }
           98  +  }
           99  +  return false;
          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 string& Expected, const string& 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(_, VisitALot().travel(R, C, obsr, obsc));}
          117  +int main(){
          118  +
          119  +CASE(0)
          120  + int R = 2;
          121  + int C = 3;
          122  + vector <int> obsr;
          123  + vector <int> obsc;
          124  + string _ = "SENE";
          125  +END
          126  +CASE(1)
          127  + int R = 6;
          128  + int C = 5;
          129  + int obsr_[] = {1, 1, 4};
          130  +   vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_));
          131  + int obsc_[] = {1, 3, 1};
          132  +   vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_));
          133  + string _ = "SSEESWWSSEENEE";
          134  +END
          135  +CASE(2)
          136  + int R = 7;
          137  + int C = 8;
          138  + vector <int> obsr;
          139  + vector <int> obsc;
          140  + string _ = "EEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEE";
          141  +END
          142  +CASE(3)
          143  + int R = 7;
          144  + int C = 4;
          145  + int obsr_[] = { 5,2,1 };
          146  +   vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_));
          147  +   int obsc_[] = { 1,2,2 };
          148  +   vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_));
          149  + string _ = "?";
          150  +END
          151  +CASE(4)
          152  + int R = 50;
          153  + int C = 50;
          154  + int obsr_[] = { 1,10,15 };
          155  +   vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_));
          156  +   int obsc_[] = { 28, 17, 3 };
          157  +   vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_));
          158  + string _ = "?";
          159  +END
          160  +CASE(4)
          161  +int R = 5;
          162  +int C = 5;
          163  +int obsr_[] = { 1,2,3 };
          164  +vector <int> obsr(obsr_, obsr_ + sizeof(obsr_) / sizeof(*obsr_));
          165  +int obsc_[] = { 1,2,3 };
          166  +vector <int> obsc(obsc_, obsc_ + sizeof(obsc_) / sizeof(*obsc_));
          167  +string _ = "?";
          168  +END
          169  +CASE(4)
          170  +int R = 4;
          171  +int C = 4;
          172  +int obsr_[] = { 1,2 };
          173  +vector <int> obsr(obsr_, obsr_ + sizeof(obsr_) / sizeof(*obsr_));
          174  +int obsc_[] = { 1,2 };
          175  +vector <int> obsc(obsc_, obsc_ + sizeof(obsc_) / sizeof(*obsc_));
          176  +string _ = "?";
          177  +END
          178  +}
          179  +// END CUT HERE

Added SRM/TCO20-3B-U/1B.cpp version [2ee42b04a811c9f2]

            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  +class ShortBugPaths { public:
           39  + int count(int N, vector <int> D, int J)
           40  + {
           41  +  if (N <= 200) {
           42  +   vector<vector<int>> c(N, vector<int>(N, 1));
           43  +   vector<vector<int>> c2(N, vector<int>(N, 1));
           44  +   for (int _ = 0; _ < J; ++_) {
           45  +    for (int y = 0; y < N; ++y)
           46  +    for (int x = 0; x < N; ++x) {
           47  +     LL sum = 0;
           48  +     for (int DD : D) {
           49  +      int yy = y - DD, xx = x;
           50  +      for (int d = 0; d < DD; ++d) {
           51  +       if (0 <= yy&&yy<N && 0 <= xx&&xx<N) sum += c[yy][xx];
           52  +       yy++, xx++;
           53  +      }
           54  +      for (int d = 0; d < DD; ++d) {
           55  +       if (0 <= yy&&yy<N && 0 <= xx&&xx<N) sum += c[yy][xx];
           56  +       yy++, xx--;
           57  +      }
           58  +      for (int d = 0; d < DD; ++d) {
           59  +       if (0 <= yy&&yy<N && 0 <= xx&&xx<N) sum += c[yy][xx];
           60  +       yy--, xx--;
           61  +      }
           62  +      for (int d = 0; d < DD; ++d) {
           63  +       if (0 <= yy&&yy<N && 0 <= xx&&xx<N) sum += c[yy][xx];
           64  +       yy--, xx++;
           65  +      }
           66  +      if (DD == 0)
           67  +       sum += c[y][x];
           68  +     }
           69  +     c2[y][x] = sum % MODVAL;
           70  +    }
           71  +    c.swap(c2);
           72  +   }
           73  +   mint ans = 0;
           74  +   for (int y = 0; y < N; ++y)
           75  +    for (int x = 0; x < N; ++x)
           76  +     ans += c[y][x];
           77  +   return ans.val;
           78  +  }
           79  +  else {
           80  +   vector<vector<int>> c(201, vector<int>(201, 1));
           81  +   vector<vector<int>> c2(201, vector<int>(201, 1));
           82  +   for (int _ = 0; _ < J; ++_) {
           83  +    for (int y = 0; y < 101; ++y)
           84  +     for (int x = 0; x < 101; ++x) {
           85  +      LL sum = 0;
           86  +      for (int DD : D) {
           87  +       int yy = y - DD, xx = x;
           88  +
           89  +       if (y == 100 && x == 100) {
           90  +        for (int d = 0; d < DD; ++d) {
           91  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][100];
           92  +         yy++, xx++;
           93  +        }
           94  +        for (int d = 0; d < DD; ++d) {
           95  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][100];
           96  +         yy++, xx--;
           97  +        }
           98  +        for (int d = 0; d < DD; ++d) {
           99  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][100];
          100  +         yy--, xx--;
          101  +        }
          102  +        for (int d = 0; d < DD; ++d) {
          103  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][100];
          104  +         yy--, xx++;
          105  +        }
          106  +       }
          107  +       else if (y == 100) {
          108  +        for (int d = 0; d < DD; ++d) {
          109  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][min(100,xx)];
          110  +         yy++, xx++;
          111  +        }
          112  +        for (int d = 0; d < DD; ++d) {
          113  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][min(100, xx)];
          114  +         yy++, xx--;
          115  +        }
          116  +        for (int d = 0; d < DD; ++d) {
          117  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][min(100, xx)];
          118  +         yy--, xx--;
          119  +        }
          120  +        for (int d = 0; d < DD; ++d) {
          121  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[100][min(100, xx)];
          122  +         yy--, xx++;
          123  +        }
          124  +       }
          125  +       else if (x == 100) {
          126  +        for (int d = 0; d < DD; ++d) {
          127  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][100];
          128  +         yy++, xx++;
          129  +        }
          130  +        for (int d = 0; d < DD; ++d) {
          131  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][100];
          132  +         yy++, xx--;
          133  +        }
          134  +        for (int d = 0; d < DD; ++d) {
          135  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][100];
          136  +         yy--, xx--;
          137  +        }
          138  +        for (int d = 0; d < DD; ++d) {
          139  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][100];
          140  +         yy--, xx++;
          141  +        }
          142  +       }
          143  +       else {
          144  +        for (int d = 0; d < DD; ++d) {
          145  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][min(100, xx)];
          146  +         yy++, xx++;
          147  +        }
          148  +        for (int d = 0; d < DD; ++d) {
          149  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][min(100, xx)];
          150  +         yy++, xx--;
          151  +        }
          152  +        for (int d = 0; d < DD; ++d) {
          153  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][min(100, xx)];
          154  +         yy--, xx--;
          155  +        }
          156  +        for (int d = 0; d < DD; ++d) {
          157  +         if (0 <= yy&&yy < N && 0 <= xx&&xx < N) sum += c[min(100, yy)][min(100, xx)];
          158  +         yy--, xx++;
          159  +        }
          160  +       }
          161  +
          162  +       if (DD == 0)
          163  +        sum += c[y][x];
          164  +      }
          165  +      c2[y][x] = sum % MODVAL;
          166  +     }
          167  +    for (int y = 0; y < 201; ++y)
          168  +     for (int x = 0; x < 201; ++x)
          169  +      c2[y][x] = c2[y>100 ? 200-y : y][x>100 ? 200-x : x];
          170  +    c.swap(c2);
          171  +   }
          172  +   mint ans = 0;
          173  +   for (int y = 0; y < 201; ++y)
          174  +    for (int x = 0; x < 201; ++x)
          175  +     if (y == 100 && x == 100)
          176  +      ans += mint(c[y][x]) * (N - 200) * (N - 200);
          177  +     else if (y == 100 || x == 100)
          178  +      ans += mint(c[y][x]) * (N - 200);
          179  +     else
          180  +      ans += c[y][x];
          181  +   return ans.val;
          182  +  }
          183  + }
          184  +};
          185  +
          186  +// BEGIN CUT HERE
          187  +#include <ctime>
          188  +double start_time; string timer()
          189  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          190  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          191  + { os << "{ ";
          192  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          193  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          194  +void verify_case(const int& Expected, const int& Received) {
          195  + bool ok = (Expected == Received);
          196  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          197  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          198  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          199  +#define END  verify_case(_, ShortBugPaths().count(N, D, J));}
          200  +int main(){
          201  +
          202  +CASE(0)
          203  + int N = 3;
          204  + int D_[] = {1};
          205  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          206  + int J = 1;
          207  + int _ = 24;
          208  +END
          209  +CASE(1)
          210  + int N = 123456789;
          211  + int D_[] = {0};
          212  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          213  + int J = 3;
          214  + int _ = 643499475;
          215  +END
          216  +CASE(2)
          217  + int N = 5;
          218  + int D_[] = {0, 10, 2};
          219  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          220  + int J = 4;
          221  + int _ = 38281;
          222  +END
          223  +CASE(3)
          224  + int N = 1000;
          225  + int D_[] = {0,1};
          226  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          227  + int J = 1;
          228  + int _ = 4996000;
          229  +END
          230  +CASE(4)
          231  + int N = 47;
          232  + int D_[] = {3};
          233  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          234  + int J = 6;
          235  + int _ = 195354165;
          236  +END
          237  +CASE(5)
          238  + int N = 200;
          239  + int D_[] = { 0,1,2,3,4,5,6,7,8,9,10 };
          240  +   vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          241  + int J = 10;
          242  + int _ = 316860289;
          243  +END
          244  +CASE(6)
          245  + int N = 1000000000;
          246  + int D_[] = { 0,1,2,3,4,5,6,7,8,9,10 };
          247  + vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_));
          248  + int J = 10;
          249  + int _ = -100;
          250  +END
          251  +}
          252  +// END CUT HERE