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

Added SRM/650-U/1A.cpp version [2ee706699e24611b]

            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  +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 TaroFillingAStringDiv1 { public:
           43  + int getNumber(int, vector <int> position, string value)
           44  + {
           45  +  vector<pair<int,char>> sorted;
           46  +  for(int i=0; i<position.size(); ++i)
           47  +   sorted.emplace_back(position[i]-1, value[i]);
           48  +  sort(sorted.begin(), sorted.end());
           49  +
           50  +  mint ans = 1;
           51  +  for(int i=1; i<sorted.size(); ++i)
           52  +   ans *= solve(sorted[i].first-sorted[i-1].first-1, sorted[i-1].second == sorted[i].second);
           53  +  return ans.val;
           54  + }
           55  +
           56  + // 'A' + '?'*N + (same?'A':'B')
           57  + mint solve(int N, bool same) {
           58  +  if(same && (N%2)==1)
           59  +   return 1;
           60  +  if(!same && (N%2)==0)
           61  +   return 1;
           62  +  return (N+1);
           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(_, TaroFillingAStringDiv1().getNumber(N, position, value));}
           80  +int main(){
           81  +
           82  +CASE(0)
           83  + int N = 3;
           84  + int position_[] = {1, 3};
           85  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
           86  + string value = "AB";
           87  + int _ = 2;
           88  +END
           89  +CASE(1)
           90  + int N = 4;
           91  + int position_[] = {2, 1, 3, 4};
           92  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
           93  + string value = "ABBA";
           94  + int _ = 1;
           95  +END
           96  +CASE(2)
           97  + int N = 25;
           98  + int position_[] = {23, 4, 8, 1, 24, 9, 16, 17, 6, 2, 25, 15, 14, 7, 13};
           99  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
          100  + string value = "ABBBBABABBAAABA";
          101  + int _ = 1;
          102  +END
          103  +CASE(3)
          104  + int N = 305;
          105  + int position_[] = {183, 115, 250, 1, 188, 193, 163, 221, 144, 191, 92, 192, 58, 215, 157, 187, 227, 177, 206, 15, 272, 232, 49, 11, 178, 59, 189, 246};
          106  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
          107  + string value = "ABAABBABBAABABBBBAAAABBABBBA";
          108  + int _ = 43068480;
          109  +END
          110  +CASE(4)
          111  + int N = 1000000000;
          112  + int position_[] = {183, 115, 250, 1, 188, 193, 163, 221, 144, 191, 92, 192, 58, 215, 157, 187, 227, 177, 206, 15, 272, 232, 49, 11, 178, 59, 189, 246};
          113  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
          114  + string value = "ABAABBABBAABABBBBAAAABBABBBA";
          115  + int _ = -1;
          116  +END
          117  +/*
          118  +CASE(5)
          119  + int N = ;
          120  + int position_[] = ;
          121  +   vector <int> position(position_, position_+sizeof(position_)/sizeof(*position_));
          122  + string value = ;
          123  + int _ = ;
          124  +END
          125  +*/
          126  +}
          127  +// END CUT HERE

Added SRM/650-U/1B-U.cpp version [fc06f1f14b091ef5]

            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 TheKingsRoadsDiv1 { public:
           23  + string getAnswer(int h, vector <int> a, vector <int> b)
           24  + {
           25  +  return solve(h, a, b) ? "Correct" : "Incorrect";
           26  + }
           27  +
           28  + bool solve(int h, const vector<int>& a, const vector<int>& b)
           29  + {
           30  +  // remove obvious abnormality
           31  +  set<pair<int,int>> e;
           32  +  for(int i=0; i<a.size(); ++i)
           33  +   if(a[i] != b[i])
           34  +    e.emplace(min(a[i]-1, b[i]-1), max(a[i]-1,b[i]-1)); // I love 0-based indexing.
           35  +
           36  +  if(e.size()+3 < a.size())
           37  +   return false;
           38  +
           39  +  const int added = e.size() - ((1<<h)-2);
           40  +  const int N = (1<<h)-1;
           41  +  vector<vector<int>> g(N);
           42  +  for(auto ab: e) {
           43  +   g[ab.first].emplace_back(ab.second);
           44  +   g[ab.second].emplace_back(ab.first);
           45  +  }
           46  +
           47  +  set<pair<int,int>> susp_edges = e;
           48  +
           49  +  vector<int> det_height(N, 0);
           50  +  vector<vector<int>> det_child(N);
           51  +  vector<int> det_parent(N, -1);
           52  +  vector<int> Q;
           53  +  for(int v=0; v<N; ++v) {
           54  +   if(g[v].empty())
           55  +    return false;
           56  +   if(g[v].size() == 1) {
           57  +    det_height[v] = 1;
           58  +    Q.emplace_back(g[v].front());
           59  +   }
           60  +  }
           61  +
           62  +  for(int dh=2; dh<=h; ++dh) {
           63  +   vector<int> Q2;
           64  +   for(int v: Q) {
           65  +    if(det_height[v] == dh)
           66  +     continue;
           67  +    else if(det_height[v] == 0) {
           68  +     det_height[v] = dh;
           69  +     vector<int> cand;
           70  +     for(int u: g[v])
           71  +      if(det_height[u] == 0)
           72  +       cand.push_back(u);
           73  +     if(dh==h)
           74  +      det_parent[v] = -2;
           75  +     if(cand.size() == 1 && dh<h) {
           76  +      int u = cand.front();
           77  +      Q2.push_back(u);
           78  +      det_child[u].emplace_back(v);
           79  +      det_parent[v] = u;
           80  +      if(det_child[u].size() > 2)
           81  +       return false;
           82  +      susp_edges.erase(make_pair(min(v,u), max(v,u)));
           83  +     }
           84  +    } else {
           85  +     return false;
           86  +    }
           87  +   }
           88  +   Q.swap(Q2);
           89  +  }
           90  +
           91  +  queue<int> QQ;
           92  +  for(int v=0; v<N; ++v)
           93  +   QQ.push(v);
           94  +  while(!QQ.empty()){
           95  +   int v = QQ.front(); QQ.pop();
           96  +   if(det_height[v]==0 || det_parent[v]!=-1)
           97  +    continue;
           98  +
           99  +   vector<int> cand;
          100  +   for(int u: g[v])
          101  +    if(det_height[u] == det_height[v]+1 || det_height[u]==0)
          102  +     cand.push_back(u);
          103  +   if(cand.size() == 1) {
          104  +    int u = cand.front();
          105  +    QQ.push(u);
          106  +    det_child[u].emplace_back(v);
          107  +    det_parent[v] = u;
          108  +    if(det_child[u].size() > 2)
          109  +     return false;
          110  +    susp_edges.erase(make_pair(min(v,u), max(v,u)));
          111  +   }
          112  +  }
          113  +
          114  +  int cnt = 0;
          115  +  for(int dh: det_height)
          116  +   if(dh)
          117  +    ++cnt;
          118  +  cerr << cnt << " / " << N << " @ " << susp_edges.size() << endl;
          119  +  return susp_edges.size() == added;
          120  + }
          121  +};
          122  +
          123  +// BEGIN CUT HERE
          124  +#include <ctime>
          125  +double start_time; string timer()
          126  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          127  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          128  + { os << "{ ";
          129  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          130  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          131  +void verify_case(const string& Expected, const string& Received) {
          132  + bool ok = (Expected == Received);
          133  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          134  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          135  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          136  +#define END  verify_case(_, TheKingsRoadsDiv1().getAnswer(h, a, b));}
          137  +int main(){
          138  +
          139  +CASE(0)
          140  + int h = 3;
          141  + int a_[] = {1, 3, 2, 2, 3, 7, 1, 5, 4};
          142  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          143  + int b_[] = {6, 5, 4, 7, 4, 3, 3, 1, 7};
          144  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          145  + string _ = "Correct";
          146  +END
          147  +CASE(1)
          148  + int h = 2;
          149  + int a_[] = {1, 2, 1, 3, 3};
          150  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          151  + int b_[] = {2, 1, 2, 3, 3};
          152  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          153  + string _ = "Incorrect";
          154  +END
          155  +CASE(2)
          156  + int h = 3;
          157  + int a_[] = {1, 3, 2, 2, 6, 6, 4, 4, 7};
          158  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          159  + int b_[] = {2, 1, 4, 5, 4, 4, 7, 7, 6};
          160  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          161  + string _ = "Incorrect";
          162  +END
          163  +CASE(3)
          164  + int h = 2;
          165  + int a_[] = {1, 2, 2, 1, 1};
          166  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          167  + int b_[] = {1, 2, 2, 1, 2};
          168  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          169  + string _ = "Incorrect";
          170  +END
          171  +CASE(4)
          172  + int h = 5;
          173  + int a_[] = {6, 15, 29, 28, 7, 13, 13, 23, 28, 13, 30, 27, 14, 4, 14, 19, 27, 20, 20, 19, 10, 15, 7, 7, 19, 29, 4, 24, 10, 23, 30, 6, 24};
          174  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          175  + int b_[] = {9, 22, 30, 20, 26, 25, 8, 7, 24, 21, 27, 31, 4, 28, 29, 6, 16, 1, 17, 10, 3, 12, 30, 18, 14, 23, 19, 21, 5, 13, 15, 2, 11};
          176  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          177  + string _ = "Correct";
          178  +END
          179  +CASE(5)
          180  + int h = 2;
          181  + int a_[] = {1,1,1,2,1};
          182  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          183  + int b_[] = {2,3,1,2,2};
          184  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          185  + string _ = "Correct";
          186  +END
          187  +/*
          188  +CASE(6)
          189  + int h = ;
          190  + int a_[] = ;
          191  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          192  + int b_[] = ;
          193  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          194  + string _ = ;
          195  +END
          196  +CASE(7)
          197  + int h = ;
          198  + int a_[] = ;
          199  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          200  + int b_[] = ;
          201  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          202  + string _ = ;
          203  +END
          204  +*/
          205  +}
          206  +// END CUT HERE