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

Added SRM/TCO13-3C-U/1A.cpp version [03422e036f8b28bb]

            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 SubstringReversal { public:
           23  + vector <int> solve(string S)
           24  + {
           25  +  multiset<char> chars;
           26  +  for(char c: S) chars.insert(c);
           27  +
           28  +  string T = S;
           29  +  for(int i=0; i<S.size(); ++i) {
           30  +   if(S[i] == *chars.begin()) {
           31  +    chars.erase(chars.begin());
           32  +    continue;
           33  +   }
           34  +
           35  +   // here is the point.
           36  +   int best_k = i;
           37  +   string best = S.substr(i);
           38  +   for(int k=i+1; k<S.size(); ++k) {
           39  +    string T(S.begin()+i, S.begin()+k+1);
           40  +    reverse(T.begin(), T.end());
           41  +    T += S.substr(k+1);
           42  +    if(best > T)
           43  +     best=T, best_k=k;
           44  +   }
           45  +   vector<int> ans;
           46  +   ans.push_back(i);
           47  +   ans.push_back(best_k);
           48  +   return ans;
           49  +  }
           50  +
           51  +  // no need to reverse
           52  +  vector<int> ans;
           53  +  ans.push_back(0);
           54  +  ans.push_back(0);
           55  +  return ans;
           56  + }
           57  +};
           58  +
           59  +// BEGIN CUT HERE
           60  +#include <ctime>
           61  +double start_time; string timer()
           62  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           63  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           64  + { os << "{ ";
           65  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           66  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           67  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           68  + bool ok = (Expected == Received);
           69  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           70  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           71  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           72  +#define END  verify_case(_, SubstringReversal().solve(S));}
           73  +int main(){
           74  +
           75  +CASE(0)
           76  + string S = "abdc";
           77  + int __[] = {2, 3 };
           78  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           79  +END
           80  +CASE(1)
           81  + string S = "aabbcc";
           82  + int __[] = {0, 0 };
           83  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           84  +END
           85  +CASE(2)
           86  + string S = "misof";
           87  + int __[] = {0, 4 };
           88  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           89  +END
           90  +CASE(3)
           91  + string S = "ivan";
           92  + int __[] = {0, 2 };
           93  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           94  +END
           95  +CASE(4)
           96  + string S = "thisseemstobeaneasyproblem";
           97  + int __[] = {0, 13 };
           98  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           99  +END
          100  +/*
          101  +CASE(5)
          102  + string S = ;
          103  + int __[] = ;
          104  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          105  +END
          106  +CASE(6)
          107  + string S = ;
          108  + int __[] = ;
          109  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          110  +END
          111  +*/
          112  +}
          113  +// END CUT HERE

Added SRM/TCO13-3C-U/1B.cpp version [f7dc591b0d55c297]

            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 CliqueGraph { public:
           23  + long long calcSum(int N, vector <int> V, vector <int> sizes)
           24  + {
           25  +  vector<vector<int>> v2c(N);
           26  +  vector<vector<int>> c2v(sizes.size());
           27  +  for(int s=0,i=0; i<sizes.size(); ++i) {
           28  +   int e = s+sizes[i];
           29  +   for(int k=s; k<e; ++k) {
           30  +    v2c[V[k]].push_back(i);
           31  +    c2v[i].push_back(V[k]);
           32  +   }
           33  +   s = e;
           34  +  }
           35  +
           36  +  LL total = 0;
           37  +  for(int v=0; v<N; ++v)
           38  +   total += calc(v, v2c, c2v);
           39  +  return total / 2;
           40  + }
           41  +
           42  + LL calc(int S, const vector<vector<int>>& v2c, const vector<vector<int>>& c2v)
           43  + {
           44  +  const int V = v2c.size(), C = c2v.size();
           45  +  vector<int>  v_d(V, -1);
           46  +  vector<bool> c_visited(C, false);
           47  +  vector<int> q(1, S);
           48  +  v_d[S] = 0;
           49  +  for(int step=1; !q.empty(); step++) {
           50  +   vector<int> cq;
           51  +   for(int v: q)
           52  +    for(int c: v2c[v]) if(!c_visited[c])
           53  +     cq.push_back(c), c_visited[c]=true;
           54  +   vector<int> q2;
           55  +   for(int c: cq)
           56  +    for(int v: c2v[c]) if(v_d[v]<0)
           57  +     q2.push_back(v), v_d[v]=step;
           58  +   q = std::move(q2);
           59  +  }
           60  +
           61  +  LL total = 0;
           62  +  for(int d: v_d)
           63  +   total += d;
           64  +  return total;
           65  + }
           66  +};
           67  +
           68  +// BEGIN CUT HERE
           69  +#include <ctime>
           70  +double start_time; string timer()
           71  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           72  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           73  + { os << "{ ";
           74  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           75  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           76  +void verify_case(const long long& Expected, const long long& Received) {
           77  + bool ok = (Expected == Received);
           78  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           79  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           80  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           81  +#define END  verify_case(_, CliqueGraph().calcSum(N, V, sizes));}
           82  +int main(){
           83  +
           84  +CASE(0)
           85  + int N = 4;
           86  + int V_[] = {0,1,2,0,3};
           87  +   vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
           88  + int sizes_[] = {3,2};
           89  +   vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_));
           90  + long long _ = 8LL;
           91  +END
           92  +CASE(1)
           93  + int N = 5;
           94  + int V_[] = {0,1,2,3,1,2,4};
           95  +   vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
           96  + int sizes_[] = {4,3};
           97  +   vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_));
           98  + long long _ = 12LL;
           99  +END
          100  +CASE(2)
          101  + int N = 15;
          102  + int V_[] = {1,3,5,7,9,11,13,0
          103  +,2,3,6,7,10,11,14,0
          104  +,4,5,6,7,12,13,14,0
          105  +,8,9,10,11,12,13,14,0};
          106  +   vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
          107  + int sizes_[] = {8,8,8,8};
          108  +   vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_));
          109  + long long _ = 130LL;
          110  +END
          111  +/*
          112  +CASE(3)
          113  + int N = ;
          114  + int V_[] = ;
          115  +   vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
          116  + int sizes_[] = ;
          117  +   vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_));
          118  + long long _ = LL;
          119  +END
          120  +CASE(4)
          121  + int N = ;
          122  + int V_[] = ;
          123  +   vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_));
          124  + int sizes_[] = ;
          125  +   vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_));
          126  + long long _ = LL;
          127  +END
          128  +*/
          129  +}
          130  +// END CUT HERE

Added SRM/TCO13-3C-U/1C-U.cpp version [aff45afb5a80e9b5]

            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 InverseRMQ { public:
           23  + string possible(int n, vector <int> A, vector <int> B, vector <int> ans)
           24  + {
           25  +  vector<tuple<int,int,int>> E;
           26  +  for(int i=0; i<A.size(); ++i)
           27  +   E.emplace_back(A[i], B[i], ans[i]);
           28  +  sort(E.begin(), E.end(), [&](const tuple<int,int,int>& lhs, const tuple<int,int,int>& rhs){
           29  +   if(get<2>(lhs) < get<2>(rhs))
           30  +    return true;
           31  +   return lhs < rhs;
           32  +  });
           33  +
           34  +  vector<pair<int,int>> filled;
           35  +  for(int i=0; i<E.size(); )
           36  +  {
           37  +   int nexti = i+1;
           38  +   for(; nexti<E.size(); ++nexti)
           39  +    if(get<2>(E[i]) != get<2>(E[nexti]))
           40  +     break;
           41  +   // inner
           42  +   int L = get<0>(E[i]);
           43  +   int R = get<1>(E[i]);
           44  +   // outer
           45  +   int l = get<0>(E[i]);
           46  +   int r = get<1>(E[i]);
           47  +   for(int a=i+1; a<nexti; ++a) {
           48  +    if(R<get<0>(E[a]) || get<1>(E[a])<L)
           49  +     return "Impossible";
           50  +    L = max(L, get<0>(E[a]));
           51  +    R = min(R, get<1>(E[a]));
           52  +    l = min(l, get<0>(E[a]));
           53  +    r = max(r, get<1>(E[a]));
           54  +   }
           55  +
           56  +   bool ok = false;
           57  +   if(filled.empty()) ok = true;
           58  +   if(!ok && has_intersection(L,R,0,filled.front().first-1)) ok = true;
           59  +   if(!ok && has_intersection(L,R,filled.back().second+1,n)) ok = true;
           60  +   if(!ok) {
           61  +    for(int i=0; i+1<filled.size(); ++i)
           62  +     if(!ok && has_intersection(L,R,filled[i].second+1,filled[i+1].first-1))
           63  +      ok=true;
           64  +   }
           65  +   if(!ok)
           66  +    return "Impossible";
           67  +
           68  +   int C = get<2>(E[i]);
           69  +
           70  +   // check: enough number of elements for [l,r]
           71  +   int space = 0;
           72  +
           73  +
           74  +   // update
           75  +   filled.emplace_back(l, r);
           76  +   sort(filled.begin(), filled.end());
           77  +   vector<pair<int,int>> f2;
           78  +   filled = f2;
           79  +   for(auto r: filled) {
           80  +    if(f2.empty() || f2.back().second+1 < r.first)
           81  +     f2.push_back(r);
           82  +    else
           83  +     f2.back().second = max(f2.back().second, r.second);
           84  +   }
           85  +
           86  +   i = nexti;
           87  +  }
           88  +  return "Possible";
           89  + }
           90  +
           91  + static bool has_intersection(int a, int b, int A, int B)
           92  + {
           93  +  return !(B<a || b<A);
           94  + }
           95  +};
           96  +
           97  +// BEGIN CUT HERE
           98  +#include <ctime>
           99  +double start_time; string timer()
          100  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          101  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          102  + { os << "{ ";
          103  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          104  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          105  +void verify_case(const string& Expected, const string& Received) {
          106  + bool ok = (Expected == Received);
          107  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          108  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          109  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          110  +#define END  verify_case(_, InverseRMQ().possible(n, A, B, ans));}
          111  +int main(){
          112  +
          113  +CASE(0)
          114  + int n = 5;
          115  + int A_[] = {1,2,4};
          116  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          117  + int B_[] = {2,4,5};
          118  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          119  + int ans_[] = {3,4,5};
          120  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          121  + string _ = "Possible";
          122  +END
          123  +CASE(1)
          124  + int n = 3;
          125  + int A_[] = {1,2,3};
          126  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          127  + int B_[] = {1,2,3};
          128  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          129  + int ans_[] = {3,3,3};
          130  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          131  + string _ = "Impossible";
          132  +END
          133  +CASE(2)
          134  + int n = 600;
          135  + int A_[] = {1,101,201,301,401,501};
          136  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          137  + int B_[] = {100,200,300,400,500,600};
          138  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          139  + int ans_[] = {100,200,300,400,500,600};
          140  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          141  + string _ = "Possible";
          142  +END
          143  +CASE(3)
          144  + int n = 1000000000;
          145  + int A_[] = {1234,1234};
          146  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          147  + int B_[] = {5678,5678};
          148  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          149  + int ans_[] = {10000,20000};
          150  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          151  + string _ = "Impossible";
          152  +END
          153  +CASE(4)
          154  + int n = 8;
          155  + int A_[] = {1,2,3,4,5,6,7,8};
          156  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          157  + int B_[] = {1,2,3,4,5,6,7,8};
          158  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          159  + int ans_[] = {4,8,2,5,6,3,7,1};
          160  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          161  + string _ = "Possible";
          162  +END
          163  +CASE(5)
          164  + int n = 1000000000;
          165  + int A_[] = {1};
          166  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          167  + int B_[] = {1000000000};
          168  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          169  + int ans_[] = {19911120};
          170  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          171  + string _ = "Impossible";
          172  +END
          173  +CASE(6)
          174  + int n = ;
          175  + int A_[] = ;
          176  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          177  + int B_[] = ;
          178  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          179  + int ans_[] = ;
          180  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          181  + string _ = ;
          182  +END
          183  +CASE(7)
          184  + int n = ;
          185  + int A_[] = ;
          186  +   vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
          187  + int B_[] = ;
          188  +   vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
          189  + int ans_[] = ;
          190  +   vector <int> ans(ans_, ans_+sizeof(ans_)/sizeof(*ans_));
          191  + string _ = ;
          192  +END
          193  +
          194  +}
          195  +// END CUT HERE