Overview
| SHA1 Hash: | 9befbbd1cfff6019d7a441dc826aaac89c956e4f |
|---|---|
| Date: | 2016-09-06 03:46:01 |
| User: | kinaba |
| Comment: | 697 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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) > 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 > 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() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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>& > 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%MODVA > 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) > 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 > 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() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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