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

Added SRM/590-U/1A.cpp version [a209bed380584b53]

            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 FoxAndChess { public:
           23  + string ableToMove(string begin, string target)
           24  + {
           25  +  return solve(cb(begin), cb(target)) ? "Possible" : "Impossible";
           26  + }
           27  +
           28  + vector<pair<char,int>> cb(string s)
           29  + {
           30  +  vector<pair<char,int>> v;
           31  +  for(int i=0; i<s.size(); ++i)
           32  +   if(s[i]!='.')
           33  +    v.emplace_back(s[i], i);
           34  +  return v;
           35  + }
           36  +
           37  + bool solve(const vector<pair<char,int>>& b, const vector<pair<char,int>>& e)
           38  + {
           39  +  if(b.size() != e.size())
           40  +   return false;
           41  +  for(int i=0; i<b.size(); ++i) {
           42  +   if(b[i].first != e[i].first)
           43  +    return false;
           44  +   if(b[i].first == 'L' && b[i].second<e[i].second)
           45  +    return false;
           46  +   if(b[i].first == 'R' && b[i].second>e[i].second)
           47  +    return false;
           48  +  }
           49  +  return true;
           50  + }
           51  +};
           52  +
           53  +// BEGIN CUT HERE
           54  +#include <ctime>
           55  +double start_time; string timer()
           56  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           57  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           58  + { os << "{ ";
           59  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           60  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           61  +void verify_case(const string& Expected, const string& Received) {
           62  + bool ok = (Expected == Received);
           63  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           64  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           65  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           66  +#define END  verify_case(_, FoxAndChess().ableToMove(begin, target));}
           67  +int main(){
           68  +
           69  +CASE(0)
           70  + string begin = "R...";
           71  + string target = "..R.";
           72  + string _ = "Possible";
           73  +END
           74  +CASE(1)
           75  + string begin = "..R.";
           76  + string target = "R...";
           77  + string _ = "Impossible";
           78  +END
           79  +CASE(2)
           80  + string begin = ".L.R.R.";
           81  + string target = "L...R.R";
           82  + string _ = "Possible";
           83  +END
           84  +CASE(3)
           85  + string begin = ".L.R.";
           86  + string target = ".R.L.";
           87  + string _ = "Impossible";
           88  +END
           89  +CASE(4)
           90  + string begin = "LRLLRLRLLRLLRLRLRL";
           91  + string target = "LRLLRLRLLRLLRLRLRL";
           92  + string _ = "Possible";
           93  +END
           94  +CASE(5)
           95  + string begin = "L";
           96  + string target = ".";
           97  + string _ = "Impossible";
           98  +END
           99  +/*
          100  +CASE(6)
          101  + string begin = ;
          102  + string target = ;
          103  + string _ = ;
          104  +END
          105  +CASE(7)
          106  + string begin = ;
          107  + string target = ;
          108  + string _ = ;
          109  +END
          110  +*/
          111  +}
          112  +// END CUT HERE

Added SRM/590-U/1B.cpp version [8a48c9e039e2e851]

            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 XorCards { public:
           23  + long long numberOfWays(vector<long long> number, long long limit)
           24  + {
           25  +  LL total = 0;
           26  +  LL req = 0;
           27  +  for(int k=62; k>=0; --k)
           28  +   if(limit & (1LL<<k))
           29  +   {
           30  +    total += sub(number, k, req);
           31  +    req |= 1LL << k;
           32  +   }
           33  +  total += sub(number, 0, req);
           34  +  return total;
           35  + }
           36  +
           37  + LL sub(vector<LL> num, int k, LL req)
           38  + {
           39  +  for(auto& v : num) v>>=k;
           40  +  return exact_equal(num, req>>k);
           41  + }
           42  +
           43  + LL exact_equal(const vector<LL>& xs, LL target)
           44  + {
           45  +  int H = 50;
           46  +  int W = xs.size();
           47  +  vector<vector<int>> M(H, vector<int>(W));
           48  +  for(int y=0; y<H; ++y)
           49  +  for(int x=0; x<W; ++x)
           50  +   M[y][x] = (xs[x]>>y)&1;
           51  +  vector<int> V(H);
           52  +  for(int y=0; y<H; ++y)
           53  +   V[y] = (target>>y)&1;
           54  +  return num_solution(H, W, M, V);
           55  + }
           56  +
           57  + LL num_solution(int H, int W, vector<vector<int>>& M, vector<int>& V)
           58  + {
           59  +  int skipx = 0;
           60  +  int y = 0;
           61  +  for(int x=0; y<H && x<W; ++x)
           62  +  {
           63  +   if(M[y][x] == 0) {
           64  +    bool found = false;
           65  +    for(int yy=y+1; yy<H; ++yy)
           66  +     if(M[yy][x] == 1) {
           67  +      swap(M[y], M[yy]);
           68  +      swap(V[y], V[yy]);
           69  +      found = true;
           70  +      break;
           71  +     }
           72  +    if(!found) {
           73  +     ++skipx;
           74  +     continue;
           75  +    }
           76  +   }
           77  +
           78  +   for(int yy=y+1; yy<H; ++yy)
           79  +    if(M[yy][x] == 1) {
           80  +     for(int xx=x; xx<W; ++xx)
           81  +      M[yy][xx] ^= M[y][xx];
           82  +     V[yy] ^= V[y];
           83  +    }
           84  +   ++y;
           85  +  }
           86  +  for(int yy=y; yy<H; ++yy)
           87  +   if(V[yy] == 1)
           88  +    return 0;
           89  +  return 1LL << skipx;
           90  + }
           91  +};
           92  +
           93  +// BEGIN CUT HERE
           94  +#include <ctime>
           95  +double start_time; string timer()
           96  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           97  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           98  + { os << "{ ";
           99  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          100  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          101  +void verify_case(const long long& Expected, const long long& Received) {
          102  + bool ok = (Expected == Received);
          103  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          104  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          105  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          106  +#define END  verify_case(_, XorCards().numberOfWays(number, limit));}
          107  +int main(){
          108  +
          109  +CASE(0)
          110  + long long number_[] = {1,2};
          111  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          112  + long long limit = 2LL;
          113  + long long _ = 3LL;
          114  +END
          115  +CASE(1)
          116  + long long number_[] = {5,5};
          117  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          118  + long long limit = 3LL;
          119  + long long _ = 2LL;
          120  +END
          121  +CASE(2)
          122  + long long number_[] = {1,2,3,4,5,6,7};
          123  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          124  + long long limit = 5LL;
          125  + long long _ = 96LL;
          126  +END
          127  +CASE(3)
          128  + long long number_[] = {123, 456, 789, 147, 258, 369, 159, 357};
          129  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          130  + long long limit = 500LL;
          131  + long long _ = 125LL;
          132  +END
          133  +CASE(4)
          134  + long long number_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
          135  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          136  + long long limit = 1000000000000000LL;
          137  + long long _ = 4294967296LL;
          138  +END
          139  +CASE(5)
          140  + long long number_[] = {1000000000000000, 999999999999999};
          141  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          142  + long long limit = 65535LL;
          143  + long long _ = 2LL;
          144  +END
          145  +CASE(6)
          146  + long long number_[] = {892821358,637693537,31021825,911417798,989152798,284478611,929786194,624328131,349242118,86796344,350424823,336624178,632226779,266072173,568692508,711852205,512468333,579346169,469280619,720923652,106128825,932999125,57927219,490494892,140637785,916813689,793075515,469189529,107539985,793418872,865662420,451333923,555332979,862325752,89326522,290303848,701668240,319909799,418021685,730702785,515002318,381415044,165516801,881368921,604262389,333836176,678197867,988945968,594771926,214252143};
          147  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          148  + long long limit = 225387446LL;
          149  + long long _ = -1LL;
          150  +END
          151  +CASE(7)
          152  +long long number_[] = {0};
          153  +   vector<long long> number(number_, number_+sizeof(number_)/sizeof(*number_));
          154  + long long limit = 1LL;
          155  + long long _ = 2LL;
          156  +END
          157  +
          158  +}
          159  +// END CUT HERE