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

Added SRM/620-U/1A-U.cpp version [7aa46e2b547e667e]

            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 PairGame { public:
           23  + int maxSum(int a, int b, int c, int d)
           24  + {
           25  +  vector<pair<int,int>> s1 = seq(a,b);
           26  +  vector<pair<int,int>> s2 = seq(c,d);
           27  +  int cand = -1;
           28  +  for(auto& p1: s1)
           29  +  for(auto& p2: s2)
           30  +   if(p1 == p2)
           31  +    cand = max(cand, p1.first + p1.second);
           32  +  return cand;
           33  + }
           34  +
           35  + vector<pair<int,int>> seq(int a, int b)
           36  + {
           37  +  vector<pair<int,int>> s;
           38  +  do {
           39  +   s.emplace_back(a, b);
           40  +   if(a<b)
           41  +    b-=a;
           42  +   else
           43  +    a-=b;
           44  +  } while(a && b);
           45  +  return s;
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const int& Expected, const int& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, PairGame().maxSum(a, b, c, d));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + int a = 1;
           67  + int b = 2;
           68  + int c = 2;
           69  + int d = 1;
           70  + int _ = 2;
           71  +END
           72  +CASE(1)
           73  + int a = 15;
           74  + int b = 4;
           75  + int c = 10;
           76  + int d = 7;
           77  + int _ = 7;
           78  +END
           79  +CASE(2)
           80  + int a = 1;
           81  + int b = 1;
           82  + int c = 10;
           83  + int d = 10;
           84  + int _ = -1;
           85  +END
           86  +CASE(3)
           87  + int a = 1000;
           88  + int b = 1001;
           89  + int c = 2000;
           90  + int d = 2001;
           91  + int _ = 1001;
           92  +END
           93  +CASE(4)
           94  + int a = 10944;
           95  + int b = 17928;
           96  + int c = 7704;
           97  + int d = 21888;
           98  + int _ = 144;
           99  +END
          100  +CASE(5)
          101  + int a = 1;
          102  + int b = 1;
          103  + int c = 1;
          104  + int d = 1;
          105  + int _ = 2;
          106  +END
          107  +/*
          108  +CASE(6)
          109  + int a = ;
          110  + int b = ;
          111  + int c = ;
          112  + int d = ;
          113  + int _ = ;
          114  +END
          115  +CASE(7)
          116  + int a = ;
          117  + int b = ;
          118  + int c = ;
          119  + int d = ;
          120  + int _ = ;
          121  +END
          122  +*/
          123  +}
          124  +// END CUT HERE

Added SRM/620-U/1B.cpp version [111eb02783edc759]

            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 CandidatesSelection { public:
           23  + string possible(vector <string> score, vector <int> result)
           24  + {
           25  +  return solve(score, result) ? "Possible" : "Impossible";
           26  + }
           27  +
           28  + bool solve(vector <string> score, vector <int> result)
           29  + {
           30  +  const int N = score.size();
           31  +  const int S = score[0].size();
           32  +
           33  +  // po[a][b] : bitmask of skill set that makes a<b.
           34  +  vector<vector<LL>> po(N, vector<LL>(N));
           35  +  for(int a=0; a<N; ++a)
           36  +  for(int b=0; b<N; ++b) if(a!=b)
           37  +  {
           38  +   LL mask = 0;
           39  +   for(int s=0; s<S; ++s)
           40  +    if(score[a][s] <= score[b][s])
           41  +     mask |= 1LL<<s;
           42  +   if(a<b)
           43  +    mask |= 1LL<<S;
           44  +   po[a][b] = mask;
           45  +  }
           46  +
           47  +  vector<vector<int>> now(1, result);
           48  +
           49  +  function<bool(LL,vector<vector<int>>)> rec;
           50  +  rec = [&](LL used, vector<vector<int>> obl) {
           51  +   LL pos = ~0LL;
           52  +   for(auto& oi: obl)
           53  +    for(int i=0; i+1<oi.size(); ++i)
           54  +     pos &= po[oi[i]][oi[i+1]];
           55  +   if(pos & (1LL<<S)) // original order is enough.
           56  +    return true;
           57  +
           58  +   bool changed = false;
           59  +   for(int s=0; s<S; ++s) if(pos & ~used & (1LL<<s)) {
           60  +    vector<vector<int>> next;
           61  +    for(auto& oi: obl) {
           62  +     vector<int> cur;
           63  +     for(int o: oi) {
           64  +      if(!cur.empty() && score[cur.back()][s] < score[o][s]) {
           65  +       changed = true;
           66  +       if(cur.size()>=2)
           67  +        next.push_back(cur);
           68  +       cur.clear();
           69  +      }
           70  +      cur.push_back(o);
           71  +     }
           72  +     if(cur.size()>=2)
           73  +      next.push_back(cur);
           74  +    }
           75  +    obl = std::move(next);
           76  +   }
           77  +   return changed && rec(used|pos, obl);
           78  +  };
           79  +  return rec(0, now);
           80  + }
           81  +
           82  +};
           83  +
           84  +// BEGIN CUT HERE
           85  +#include <ctime>
           86  +double start_time; string timer()
           87  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           88  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           89  + { os << "{ ";
           90  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           91  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           92  +void verify_case(const string& Expected, const string& Received) {
           93  + bool ok = (Expected == Received);
           94  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           95  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           96  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           97  +#define END  verify_case(_, CandidatesSelection().possible(score, result));}
           98  +int main(){
           99  +
          100  +CASE(0)
          101  + string score_[] = {"CC", "AA", "BB"};
          102  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          103  + int result_[] = {1,2,0};
          104  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          105  + string _ = "Possible";
          106  +END
          107  +CASE(1)
          108  + string score_[] = {"BAB", "ABB", "AAB", "ABA"};
          109  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          110  + int result_[] = {2,0,1,3};
          111  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          112  + string _ = "Possible";
          113  +END
          114  +CASE(2)
          115  + string score_[] = {"BAB", "ABB", "AAB", "ABA"};
          116  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          117  + int result_[] = {0, 1, 3, 2};
          118  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          119  + string _ = "Impossible";
          120  +END
          121  +CASE(3)
          122  + string score_[] = {"AAA", "ZZZ"};
          123  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          124  + int result_[] = {1, 0};
          125  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          126  + string _ = "Impossible";
          127  +END
          128  +CASE(4)
          129  + string score_[] = {"ZZZ", "AAA"};
          130  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          131  + int result_[] = {0, 1};
          132  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          133  + string _ = "Possible";
          134  +END
          135  +CASE(5)
          136  + string score_[] = {"ZYYYYX","YXZYXY","ZZZZXX","XZXYYX","ZZZYYZ","ZZXXYZ","ZYZZXZ","XZYYZX"};
          137  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          138  + int result_[] = {3,7,1,0,2,5,6,4};
          139  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          140  + string _ = "Possible";
          141  +END
          142  +/*
          143  +CASE(6)
          144  + string score_[] = ;
          145  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          146  + int result_[] = ;
          147  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          148  + string _ = ;
          149  +END
          150  +CASE(7)
          151  + string score_[] = ;
          152  +   vector <string> score(score_, score_+sizeof(score_)/sizeof(*score_));
          153  + int result_[] = ;
          154  +   vector <int> result(result_, result_+sizeof(result_)/sizeof(*result_));
          155  + string _ = ;
          156  +END
          157  +*/
          158  +}
          159  +// END CUT HERE