Overview
| SHA1 Hash: | ea210c966f95c56b372c615f0b668b91bc026019 |
|---|---|
| Date: | 2013-11-20 10:15:38 |
| User: | kinaba |
| Comment: | 596 |
| 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/596-U/1A.cpp version [c682955937bb1876]
> 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 IncrementAndDoubling { public: > 23 int getMin(vector <int> d) > 24 { > 25 int cnt = 0; > 26 for(;;++cnt) > 27 { > 28 for(auto& di : d) > 29 if(di%2 == 1) > 30 ++cnt, di--; > 31 if(count(d.begin(), d.end(), 0) == d.size()) > 32 break; > 33 for(auto& di : d) > 34 di /= 2; > 35 } > 36 return cnt; > 37 } > 38 }; > 39 > 40 // BEGIN CUT HERE > 41 #include <ctime> > 42 double start_time; string timer() > 43 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 44 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 45 { os << "{ "; > 46 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 47 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 48 void verify_case(const int& Expected, const int& Received) { > 49 bool ok = (Expected == Received); > 50 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 52 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 53 #define END verify_case(_, IncrementAndDoubling().getMin(desiredArray));} > 54 int main(){ > 55 > 56 CASE(0) > 57 int desiredArray_[] = {2, 1}; > 58 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 59 int _ = 3; > 60 END > 61 CASE(1) > 62 int desiredArray_[] = {16, 16, 16}; > 63 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 64 int _ = 7; > 65 END > 66 CASE(2) > 67 int desiredArray_[] = {100}; > 68 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 69 int _ = 9; > 70 END > 71 CASE(3) > 72 int desiredArray_[] = {0, 0, 1, 0, 1}; > 73 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 74 int _ = 2; > 75 END > 76 CASE(4) > 77 int desiredArray_[] = {123, 234, 345, 456, 567, 789}; > 78 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 79 int _ = 40; > 80 END > 81 CASE(5) > 82 int desiredArray_[] = {7,5,8,1,8,6,6,5,3,5,5,2,8,9,9,4,6,9,4,4,1,9,9,2,8 > 83 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 84 int _ = 84; > 85 END > 86 /* > 87 CASE(6) > 88 int desiredArray_[] = ; > 89 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 90 int _ = ; > 91 END > 92 CASE(7) > 93 int desiredArray_[] = ; > 94 vector <int> desiredArray(desiredArray_, desiredArray_+sizeof(desiredA > 95 int _ = ; > 96 END > 97 */ > 98 } > 99 // END CUT HERE
Added SRM/596-U/1B.cpp version [0026c7bfbd49720a]
> 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 BitwiseAnd { public: > 23 vector<long long> lexSmallest(vector<long long> subset, int N) > 24 { > 25 vector<LL> FAIL; > 26 > 27 // precheck > 28 for(int i=0; i<subset.size(); ++i) > 29 for(int j=i+1; j<subset.size(); ++j) > 30 if((subset[i]&subset[j])==0) > 31 return FAIL; > 32 for(int i=0; i<subset.size(); ++i) > 33 for(int j=i+1; j<subset.size(); ++j) > 34 for(int k=j+1; k<subset.size(); ++k) > 35 if((subset[i]&subset[j]&subset[k])!=0) > 36 return FAIL; > 37 > 38 vector<LL> ans = subset; > 39 > 40 LL rest = (1LL<<60)-1; > 41 vector<LL> leftbits = subset; > 42 for(int i=0; i<subset.size(); ++i) > 43 { > 44 rest &= ~subset[i]; > 45 for(int k=0; k<leftbits.size(); ++k) if(k!=i) > 46 leftbits[k] &= ~ subset[i]; > 47 } > 48 > 49 while(leftbits.size() < N) > 50 { > 51 LL v = 0; > 52 for(int i=0; i<leftbits.size(); ++i) > 53 { > 54 if(leftbits[i] == 0) > 55 return FAIL; > 56 LL least = 1; > 57 while((leftbits[i] & least)==0) > 58 least <<= 1; > 59 leftbits[i] &= ~least; > 60 v |= least; > 61 } > 62 > 63 LL restv = 0; > 64 int needbits = (N - leftbits.size() - 1); > 65 while(needbits--) { > 66 if(rest == 0) > 67 return FAIL; > 68 LL least = 1; > 69 while((rest & least)==0) > 70 least <<= 1; > 71 rest &= ~least; > 72 restv |= least; > 73 } > 74 > 75 leftbits.push_back(restv); > 76 ans.push_back(v | restv); > 77 } > 78 > 79 sort(ans.begin(), ans.end()); > 80 return ans; > 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) > 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 > 92 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 93 bool ok = (Expected == Received); > 94 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 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(_, BitwiseAnd().lexSmallest(subset, N));} > 98 int main(){ > 99 > 100 CASE(0) > 101 long long subset_[] = {14, 20}; > 102 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 103 int N = 3; > 104 long long __[] = {14, 18, 20 }; > 105 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 106 END > 107 CASE(1) > 108 long long subset_[] = {11, 17, 20}; > 109 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 110 int N = 4; > 111 vector<long long> _; > 112 END > 113 CASE(2) > 114 long long subset_[] = {99, 157}; > 115 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 116 int N = 4; > 117 long long __[] = {99, 157, 262, 296 }; > 118 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 119 END > 120 CASE(3) > 121 long long subset_[] = {1152921504606846975}; > 122 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 123 int N = 3; > 124 vector<long long> _; > 125 END > 126 CASE(4) > 127 vector<long long> subset; > 128 int N = 5; > 129 long long __[] = {15, 113, 402, 676, 840 }; > 130 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 131 END > 132 CASE(5) > 133 long long subset_[] = {1, 3, 5, 7, 9, 11}; > 134 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 135 int N = 6; > 136 vector<long long> _; > 137 END > 138 CASE(6) > 139 long long subset_[] = {(1LL<<60)-1>>50<<50}; > 140 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 141 int N = 11; > 142 vector<long long> _; > 143 END > 144 /* > 145 CASE(7) > 146 long long subset_[] = ; > 147 vector<long long> subset(subset_, subset_+sizeof(subset_)/sizeof(*subs > 148 int N = ; > 149 long long __[] = ; > 150 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 151 END > 152 */ > 153 } > 154 // END CUT HERE