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

Added SRM/697-U/1A-U.cpp version [016b888673aa9f4b]

            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 DivisibleSetDiv1 { public:
           23  + string isPossible(vector <int> b)
           24  + {
           25  +  return solve(b) ? "Possible" : "Impossible";
           26  + }
           27  +
           28  + bool solve(vector<int> b)
           29  + {
           30  +  sort(b.begin(), b.end());
           31  +  int n = b.size();
           32  +
           33  +  int sum = 0;
           34  +  for(int i=0; i<b.size(); ++i)
           35  +   sum += (n-i);
           36  +  for(int i=0; i<b.size(); ++i)
           37  +   if(sum > (b[i]+1)*(n-i))
           38  +    return false;
           39  +  return true;
           40  + }
           41  +};
           42  +
           43  +// BEGIN CUT HERE
           44  +#include <ctime>
           45  +double start_time; string timer()
           46  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           47  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           48  + { os << "{ ";
           49  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           50  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           51  +void verify_case(const string& Expected, const string& Received) {
           52  + bool ok = (Expected == Received);
           53  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           54  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           55  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           56  +#define END  verify_case(_, DivisibleSetDiv1().isPossible(b));}
           57  +int main(){
           58  +
           59  +CASE(0)
           60  + int b_[] = {2,1};
           61  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           62  + string _ = "Possible";
           63  +END
           64  +CASE(1)
           65  + int b_[] = {1,1};
           66  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           67  + string _ = "Impossible";
           68  +END
           69  +CASE(2)
           70  + int b_[] = {7, 7, 7};
           71  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           72  + string _ = "Possible";
           73  +END
           74  +CASE(3)
           75  + int b_[] = {5,3,5,4,6,1,3,7,9,6,2,5,4,1,1,9,6,10,10,6,10,7,7,8};
           76  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           77  + string _ = "Impossible";
           78  +END
           79  +CASE(4)
           80  + int b_[] = {2,3,4};
           81  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           82  + string _ = "Possible";
           83  +END
           84  +/*
           85  +CASE(5)
           86  + int b_[] = ;
           87  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
           88  + string _ = ;
           89  +END
           90  +*/
           91  +}
           92  +// END CUT HERE

Added SRM/697-U/1B.cpp version [ca93294461342c9b]

            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  +
           24  +class XorOrderDiv1 { public:
           25  + int get(int m, int n, int a0, int b)
           26  + {
           27  +  vector<int> a;
           28  +  for(int i=0; i<n; ++i)
           29  +   a.push_back(int((a0 + LL(i)*b) % (1LL<<m)));
           30  +  sort(a.begin(), a.end());
           31  +  return solve(a, m);
           32  + }
           33  +
           34  + int solve(const vector<int>& A, int M)
           35  + {
           36  +  vector<int> d;
           37  +  return solve_rec(A, 0, A.size(), M-1, d);
           38  + }
           39  +
           40  + int solve_rec(const vector<int>& A, int s, int e, int bit, vector<int>& d)
           41  + {
           42  +  if(s==e)
           43  +   return 0;
           44  +
           45  +  if(bit == -1) {
           46  +   const int M = d.size();
           47  +   LL q = 0;
           48  +   LL sigma = 0;
           49  +   for(int m=M-1; m>=0; --m)
           50  +   {
           51  +    LL qprev = q;
           52  +    LL dd = d[m];
           53  +    q = dd*dd%MODVAL*(1LL<<(M-m-1)) + sigma*dd%MODVAL*(1LL<<(M-m-1)) + 2*qprev;
           54  +    sigma += dd;
           55  +   }
           56  +   return int(q % MODVAL);
           57  +  }
           58  +
           59  +  int m=s;
           60  +  for(; m<e; ++m)
           61  +   if(A[m]&(1<<bit))
           62  +    break;
           63  +
           64  +  int ans = 0;
           65  +  d.push_back(e-m);
           66  +  ans ^= solve_rec(A, s, m, bit-1, d);
           67  +  d.pop_back();
           68  +  d.push_back(m-s);
           69  +  ans ^= solve_rec(A, m, e, bit-1, d);
           70  +  d.pop_back();
           71  +  return ans;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const int& Expected, const int& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, XorOrderDiv1().get(m, n, a0, b));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int m = 2;
           93  + int n = 3;
           94  + int a0 = 0;
           95  + int b = 1;
           96  + int _ = 8;
           97  +END
           98  +CASE(1)
           99  + int m = 3;
          100  + int n = 5;
          101  + int a0 = 1;
          102  + int b = 3;
          103  + int _ = 48;
          104  +END
          105  +CASE(2)
          106  + int m = 16;
          107  + int n = 100;
          108  + int a0 = 41;
          109  + int b = 5;
          110  + int _ = 523436032;
          111  +END
          112  +CASE(3)
          113  + int m = 30;
          114  + int n = 200000;
          115  + int a0 = 399;
          116  + int b = 18082016;
          117  + int _ = 408585698;
          118  +END
          119  +/*
          120  +CASE(4)
          121  + int m = ;
          122  + int n = ;
          123  + int a0 = ;
          124  + int b = ;
          125  + int _ = ;
          126  +END
          127  +CASE(5)
          128  + int m = ;
          129  + int n = ;
          130  + int a0 = ;
          131  + int b = ;
          132  + int _ = ;
          133  +END
          134  +*/
          135  +}
          136  +// END CUT HERE