Overview
| SHA1 Hash: | 4c0c9a228b4859a1529f5610c45e37fa9d718b78 |
|---|---|
| Date: | 2013-07-01 15:08:02 |
| User: | kinaba |
| Comment: | TCO13, |
| 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/TCO13-3B-U/1A.cpp version [b54e51e3de8ee5c7]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<double> CMP; > 21 > 22 const int ANY = 0; > 23 > 24 static const unsigned MODVAL = 1000000009; > 25 struct mint > 26 { > 27 unsigned val; > 28 mint():val(0){} > 29 mint(int x):val(x%MODVAL) {} > 30 mint(unsigned x):val(x%MODVAL) {} > 31 mint(LL x):val(x%MODVAL) {} > 32 }; > 33 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 34 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 35 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 36 mint operator+(mint x, mint y) { return x+=y; } > 37 mint operator-(mint x, mint y) { return x-=y; } > 38 mint operator*(mint x, mint y) { return x*=y; } > 39 > 40 class SimilarSequences { public: > 41 int count(vector <int> seq, int bound) > 42 { > 43 vector< vector<int> > cand; > 44 cand.push_back(seq); > 45 for(int i=0; i<seq.size(); ++i) > 46 { > 47 vector<int> s = seq; > 48 s.erase(s.begin() + i); > 49 s.push_back(ANY); > 50 cand.push_back(s); > 51 for(int w=s.size()-1; w>0; --w) { > 52 swap(s[w], s[w-1]); > 53 cand.push_back(s); > 54 } > 55 } > 56 vector<int> idx; > 57 for(int i=0; i<cand.size(); ++i) > 58 idx.push_back(i); > 59 return rec(0, cand, idx, bound).val; > 60 } > 61 > 62 mint rec(int I, const vector<vector<int> >& cand, const vector<int>& idx > 63 { > 64 if(idx.empty()) > 65 return 0; > 66 if(I == cand[0].size()) > 67 return 1; > 68 > 69 mint total = 0; > 70 > 71 set<int> head; > 72 for(int k=0; k<idx.size(); ++k) > 73 if( cand[idx[k]][I] != ANY ) > 74 head.insert(cand[idx[k]][I]); > 75 // Use an existing value. > 76 for(set<int>::iterator it=head.begin(); it!=head.end(); ++it) > 77 { > 78 int h = *it; > 79 vector<int> idx2; > 80 for(int k=0; k<idx.size(); ++k) > 81 if(cand[idx[k]][I]==ANY || cand[idx[k]][I]==h) > 82 idx2.push_back(idx[k]); > 83 total += rec(I+1, cand, idx2, B); > 84 } > 85 > 86 // Use nonexisting. > 87 if(B > head.size()) { > 88 vector<int> idx2; > 89 for(int k=0; k<idx.size(); ++k) > 90 if(cand[idx[k]][I]==ANY) > 91 idx2.push_back(idx[k]); > 92 total += rec(I+1, cand, idx2, B) * (B - head.size()); > 93 } > 94 > 95 return total; > 96 } > 97 }; > 98 > 99 // BEGIN CUT HERE > 100 #include <ctime> > 101 double start_time; string timer() > 102 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 103 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 104 { os << "{ "; > 105 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 106 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 107 void verify_case(const int& Expected, const int& Received) { > 108 bool ok = (Expected == Received); > 109 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 110 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 111 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 112 #define END verify_case(_, SimilarSequences().count(seq, bound));} > 113 int main(){ > 114 > 115 CASE(0) > 116 int seq_[] = {1, 1}; > 117 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 118 int bound = 3; > 119 int _ = 5; > 120 END > 121 CASE(1) > 122 int seq_[] = {1, 2}; > 123 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 124 int bound = 2; > 125 int _ = 4; > 126 END > 127 CASE(2) > 128 int seq_[] = {999999999}; > 129 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 130 int bound = 1000000000; > 131 int _ = 1000000000; > 132 END > 133 CASE(3) > 134 int seq_[] = {1, 2, 3, 4, 5}; > 135 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 136 int bound = 5; > 137 int _ = 97; > 138 END > 139 CASE(4) > 140 int seq_[] = {5, 8, 11, 12, 4, 1, 7, 9}; > 141 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 142 int bound = 1000000000; > 143 int _ = 999999363; > 144 END > 145 /* > 146 CASE(5) > 147 int seq_[] = ; > 148 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 149 int bound = ; > 150 int _ = ; > 151 END > 152 CASE(6) > 153 int seq_[] = ; > 154 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 155 int bound = ; > 156 int _ = ; > 157 END > 158 */ > 159 } > 160 // END CUT HERE
Added SRM/TCO13-3B-U/1B.cpp version [00e49509bf66508d]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<double> CMP; > 21 > 22 static const int INF = 999, UNK = -1; > 23 > 24 int bitcnt(int x) > 25 { > 26 int c = 0; > 27 for(; x; x>>=1) > 28 c += x&1; > 29 return c; > 30 } > 31 > 32 class AntlerSwapping { public: > 33 int getmin(vector <int> a, vector <int> b, int capacity) > 34 { > 35 int N = a.size(); > 36 vector<bool> tbl(1<<N); > 37 for(int mask=1; mask<(1<<N); ++mask) > 38 { > 39 vector<int> c; > 40 for(int i=0; (1<<i)<=mask; ++i) > 41 if((1<<i) & mask) { > 42 c.push_back(a[i]); > 43 c.push_back(b[i]); > 44 } > 45 sort(c.begin(), c.end()); > 46 bool can = true; > 47 for(int i=0; i+1<c.size(); i+=2) > 48 if(abs(c[i]-c[i+1]) > capacity) > 49 can = false; > 50 tbl[mask] = can; > 51 } > 52 vector<int> memo(1<<N, UNK); > 53 int best = rec((1<<N)-1, tbl, memo); > 54 return best>=INF ? -1 : best; > 55 } > 56 > 57 int rec(int mask, const vector<bool>& tbl, vector<int>& memo) > 58 { > 59 if(memo[mask] != UNK) > 60 return memo[mask]; > 61 if(mask == 0) > 62 return 0; > 63 int best = INF; > 64 for(int m2=mask; m2; m2=(m2-1)&mask) > 65 { > 66 int bc = bitcnt(m2); > 67 if(tbl[m2]) > 68 best = min(best, (bc-1) + rec(mask&~m2, tbl, mem > 69 } > 70 return memo[mask] = best; > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const int& Expected, const int& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, AntlerSwapping().getmin(antler1, antler2, capaci > 88 int main(){ > 89 > 90 CASE(0) > 91 int antler1_[] = {3, 2, 2}; > 92 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 93 int antler2_[] = {3, 5, 5}; > 94 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 95 int capacity = 0; > 96 int _ = 1; > 97 END > 98 CASE(1) > 99 int antler1_[] = {4, 2, 6, 4, 8, 5, 2, 3}; > 100 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 101 int antler2_[] = {3, 4, 5, 2, 8, 5, 7, 6}; > 102 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 103 int capacity = 1; > 104 int _ = 2; > 105 END > 106 CASE(2) > 107 int antler1_[] = {12, 34, 56, 78}; > 108 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 109 int antler2_[] = {1234, 2345, 3456, 4567}; > 110 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 111 int capacity = 100; > 112 int _ = -1; > 113 END > 114 CASE(3) > 115 int antler1_[] = {47, 58, 2013}; > 116 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 117 int antler2_[] = {49, 55, 2013}; > 118 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 119 int capacity = 3; > 120 int _ = 0; > 121 END > 122 CASE(4) > 123 int antler1_[] = {4, 1, 7, 5, 7, 8, 2, 1, 3, 1, 7, 5, 9, 4, 9, 1}; > 124 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 125 int antler2_[] = {10, 6, 5, 3, 1, 8, 4, 4, 4, 7, 1, 4, 6, 5, 10, 10}; > 126 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 127 int capacity = 1; > 128 int _ = 7; > 129 END > 130 /* > 131 CASE(5) > 132 int antler1_[] = ; > 133 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 134 int antler2_[] = ; > 135 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 136 int capacity = ; > 137 int _ = ; > 138 END > 139 CASE(6) > 140 int antler1_[] = ; > 141 vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antle > 142 int antler2_[] = ; > 143 vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antle > 144 int capacity = ; > 145 int _ = ; > 146 END > 147 */ > 148 } > 149 // END CUT HERE