Overview
| SHA1 Hash: | 0ea7f42c5c7e4bf70d89d72b50e7488f4d356a3a |
|---|---|
| Date: | 2012-09-02 11:59:33 |
| User: | kinaba |
| Comment: | 554 |
| 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/554/1A.cpp version [564dff6445080d46]
> 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<LD> CMP; > 21 > 22 class TheBrickTowerEasyDivOne { public: > 23 int find(int redCount, int redHeight, int blueCount, int blueHeight) > 24 { > 25 if(redHeight != blueHeight) > 26 { > 27 int ans = 0; > 28 ans += min(redCount, blueCount); > 29 ans += min(redCount-1, blueCount) + 1; > 30 ans += min(redCount, blueCount-1) + 1; > 31 return ans; > 32 } > 33 return min(redCount,blueCount)*2 + (redCount != blueCount); > 34 } > 35 }; > 36 > 37 // BEGIN CUT HERE > 38 #include <ctime> > 39 double start_time; string timer() > 40 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 41 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 42 { os << "{ "; > 43 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 44 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 45 void verify_case(const int& Expected, const int& Received) { > 46 bool ok = (Expected == Received); > 47 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 48 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 49 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 50 #define END verify_case(_, TheBrickTowerEasyDivOne().find(redCount, redHeig > 51 int main(){ > 52 > 53 CASE(0) > 54 int redCount = 1; > 55 int redHeight = 2; > 56 int blueCount = 3; > 57 int blueHeight = 4; > 58 int _ = 4; > 59 END > 60 CASE(1) > 61 int redCount = 4; > 62 int redHeight = 4; > 63 int blueCount = 4; > 64 int blueHeight = 7; > 65 int _ = 12; > 66 END > 67 CASE(2) > 68 int redCount = 7; > 69 int redHeight = 7; > 70 int blueCount = 4; > 71 int blueHeight = 4; > 72 int _ = 13; > 73 END > 74 CASE(3) > 75 int redCount = 47; > 76 int redHeight = 47; > 77 int blueCount = 47; > 78 int blueHeight = 47; > 79 int _ = 94; > 80 END > 81 /* > 82 CASE(4) > 83 int redCount = ; > 84 int redHeight = ; > 85 int blueCount = ; > 86 int blueHeight = ; > 87 int _ = ; > 88 END > 89 CASE(5) > 90 int redCount = ; > 91 int redHeight = ; > 92 int blueCount = ; > 93 int blueHeight = ; > 94 int _ = ; > 95 END > 96 */ > 97 } > 98 // END CUT HERE
Added SRM/554/1B.cpp version [473b414db01c6264]
> 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<LD> CMP; > 21 > 22 class TheBrickTowerMediumDivOne { public: > 23 vector <int> find(vector<int> heights) > 24 { > 25 const int N = heights.size(); > 26 const int best = best_for(heights); > 27 vector<bool> used(N, false); > 28 vector<int> answer; > 29 vector<int> current; > 30 int current_score = 0; > 31 for(int i=0; i<N; ++i) > 32 { > 33 for(int k=0; k<N; ++k) if(!used[k]) > 34 { > 35 vector<int> hh; > 36 for(int a=0; a<N; ++a) if(!used[a] && a!=k) > 37 hh.push_back(heights[a]); > 38 int ss = current_score; > 39 if(!current.empty()) ss += max(current.back(), h > 40 ss += best_for(heights[k], hh); > 41 if( ss == best ) { > 42 answer.push_back(k); > 43 if(!current.empty()) current_score += ma > 44 current.push_back(heights[k]); > 45 used[k] = true; > 46 break; > 47 } > 48 } > 49 } > 50 return answer; > 51 } > 52 > 53 int best_for(vector<int> h) > 54 { > 55 sort(h.begin(), h.end()); > 56 int best = 0; > 57 for(int i=0; i+1<h.size(); ++i) > 58 best += max(h[i], h[i+1]); > 59 return best; > 60 } > 61 > 62 int best_for(int h0, vector<int> h) > 63 { > 64 if(h.empty()) > 65 return 0; > 66 > 67 sort(h.begin(), h.end()); > 68 int best = max(h0, h[0]); > 69 for(int i=0; i+1<h.size(); ++i) > 70 best += max(h[i], h[i+1]); > 71 return best; > 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 vector <int>& Expected, const vector <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 << endl; } } > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, TheBrickTowerMediumDivOne().find(heights));} > 89 int main(){ > 90 > 91 CASE(0) > 92 int heights_[] = {4, 7, 5}; > 93 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 94 int __[] = {0, 2, 1 }; > 95 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 96 END > 97 CASE(1) > 98 int heights_[] = {4, 4, 4, 4, 4, 4, 4}; > 99 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 100 int __[] = {0, 1, 2, 3, 4, 5, 6 }; > 101 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 102 END > 103 CASE(2) > 104 int heights_[] = {2, 3, 3, 2}; > 105 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 106 int __[] = {0, 3, 1, 2 }; > 107 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 108 END > 109 CASE(3) > 110 int heights_[] = {13, 32, 38, 25, 43, 47, 6}; > 111 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 112 int __[] = {0, 6, 3, 1, 2, 4, 5 }; > 113 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 114 END > 115 CASE(4) > 116 int heights_[] = {28,36,27,33,30,18,16,23,39,31,4,40,41,41,30,43,45,16,5 > 117 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 118 vector <int> _; > 119 END > 120 CASE(5) > 121 int heights_[] = {7,34,5,15,43,8,36,5,42,22,37,45,46,38,40,2,3,22,35,23, > 122 vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heigh > 123 vector <int> _; > 124 END > 125 } > 126 // END CUT HERE
Added SRM/554/1C.cpp version [2562ed8ee62d4add]
> 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<LD> CMP; > 21 > 22 static const int MODVAL = 1234567891; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 template<typename T> > 39 vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) > 40 { > 41 int N = a.size(); > 42 vector<T> u(N); > 43 for(int i=0; i<N; ++i) > 44 for(int j=0; j<N; ++j) > 45 u[i] += a[i][j]*v[j]; > 46 return u; > 47 } > 48 > 49 template<typename T> > 50 vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> > 51 { > 52 int N = a.size(); > 53 vector< vector<T> > c(N, vector<T>(N)); > 54 for(int i=0; i<N; ++i) > 55 for(int j=0; j<N; ++j) > 56 for(int k=0; k<N; ++k) > 57 c[i][j] += a[i][k]*b[k][j]; > 58 return c; > 59 } > 60 > 61 template<typename T> > 62 vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) > 63 { > 64 int N = a.size(); > 65 vector< vector<T> > c(N, vector<T>(N)); > 66 for(int i=0; i<N; ++i) c[i][i] = 1; > 67 for(; e; e>>=1) { > 68 if(e&1) > 69 c = MATMUL(c, a); > 70 a = MATMUL(a, a); > 71 } > 72 return c; > 73 } > 74 > 75 class TheBrickTowerHardDivOne { public: > 76 int find(int C, int K, long long H) > 77 { > 78 vector< vector<int> > patterns; > 79 { > 80 vector<int> p; > 81 vector<bool> used(4); > 82 generate_patterns(true, 4, used, p, 0, patterns); > 83 } > 84 const vector<int> compress = calc_compress_table(patterns).first > 85 const vector<bool> is_repr = calc_compress_table(patterns).secon > 86 > 87 const int PN = patterns.size(); > 88 const int CPN = *max_element(compress.begin(), compress.end())+1 > 89 const int D = CPN * (K+1); > 90 > 91 vector< vector<mint> > m(D+1, vector<mint>(D+1)); > 92 for(int pa=0; pa<PN; ++pa) if(is_repr[pa]) > 93 for(int pb=0; pb<PN; ++pb) { > 94 vector<mint> tt = transition(patterns[pa], patterns[pb], > 95 for(int ka=0; ka<=K; ++ka) > 96 for(int kt=0; kt<=K; ++kt) { > 97 int kb = ka + kt + internal(patterns[pb]); > 98 if(kb <= K) > 99 m[compress[pb]*(K+1)+kb][compress[pa]*(K > 100 } > 101 } > 102 for(int x=0; x<D+1; ++x) > 103 m[D][x] = 1; > 104 > 105 vector<mint> v(D+1); > 106 for(int pa=0; pa<PN; ++pa) { > 107 int ka = internal(patterns[pa]); > 108 if(ka <= K) > 109 v[compress[pa]*(K+1)+ka] += counting(patterns[pa > 110 } > 111 > 112 v = MATMUL(MATPOW(m, H-1), v); > 113 return accumulate(v.begin(), v.end(), mint(0)).val; > 114 } > 115 > 116 // TODO: auto generate. > 117 pair< vector<int>, vector<bool> > > 118 calc_compress_table(const vector< vector<int> >& patterns) > 119 { > 120 // {0} 00,00 > 121 // {1,2,5,9} 00,01 > 122 // {3,6} 00,11 > 123 // {4,7,12,13} 00,12 > 124 // {8} 01,10 > 125 // {10,11} 01,12 > 126 // {14} 01,23 > 127 vector<int> repr(patterns.size()); > 128 vector<bool> is_repr(patterns.size(), false); > 129 is_repr[0] = true; repr[0] = 0; > 130 is_repr[1] = true; repr[1] = repr[2] = repr[5] = repr[9] = 1; > 131 is_repr[3] = true; repr[3] = repr[6] = 2; > 132 is_repr[4] = true; repr[4] = repr[7] = repr[12] = repr[13] = 3; > 133 is_repr[8] = true; repr[8] = 4; > 134 is_repr[10] = true; repr[10] = repr[11] = 5; > 135 is_repr[14] = true; repr[14] = 6; > 136 return make_pair(repr, is_repr); > 137 } > 138 > 139 mint counting(const vector<int>& p, int C) > 140 { > 141 return counting(set<int>(p.begin(), p.end()).size(), C); > 142 } > 143 > 144 mint counting(int N, int C) > 145 { > 146 if(C<0) > 147 return 0; > 148 mint v = 1; > 149 for(int i=0; i<N; ++i) > 150 v *= (C-i); > 151 return v; > 152 } > 153 > 154 int internal(const vector<int>& p) > 155 { > 156 return (p[0]==p[1])+(p[1]==p[3])+(p[3]==p[2])+(p[2]==p[0]); > 157 } > 158 > 159 vector<mint> transition(const vector<int>& pa, const vector<int>& pb, in > 160 { > 161 const int AN = set<int>(pa.begin(), pa.end()).size(); > 162 const int BN = set<int>(pb.begin(), pb.end()).size(); > 163 > 164 vector< vector<int> > patterns; > 165 { > 166 vector<int> p; > 167 vector<bool> used(AN+BN, false); > 168 generate_patterns(false, BN, used, p, AN, patterns); > 169 } > 170 > 171 vector<mint> answer(K+1); > 172 for(int i=0; i<patterns.size(); ++i) { > 173 const vector<int>& p = patterns[i]; > 174 int k = 0; > 175 for(int x=0; x<4; ++x) k += (pa[x]==p[pb[x]]); > 176 > 177 if(k <= K) { > 178 int N = max(*max_element(p.begin(), p.end()) - ( > 179 answer[k] += counting(N, C-AN); > 180 } > 181 } > 182 return answer; > 183 } > 184 > 185 void generate_patterns(bool ALLOW_DUP, int LEN, vector<bool>& used, > 186 vector<int>& p, int next, vector< vector<int> >& > 187 { > 188 if(p.size() == LEN) > 189 patterns.push_back(p); > 190 else > 191 for(int v=0; v<=next; ++v) if(ALLOW_DUP || !used[v]) { > 192 p.push_back(v); > 193 used[v] = true; > 194 generate_patterns(ALLOW_DUP, LEN, used, p, max(v > 195 used[v] = false; > 196 p.pop_back(); > 197 } > 198 } > 199 }; > 200 > 201 // BEGIN CUT HERE > 202 #include <ctime> > 203 double start_time; string timer() > 204 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 205 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 206 { os << "{ "; > 207 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 208 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 209 void verify_case(const int& Expected, const int& Received) { > 210 bool ok = (Expected == Received); > 211 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 212 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 213 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 214 #define END verify_case(_, TheBrickTowerHardDivOne().find(C, K, H));} > 215 int main(){ > 216 CASE(0) > 217 int C = 2; > 218 int K = 0; > 219 long long H = 2LL; > 220 int _ = 4; > 221 END > 222 CASE(2) > 223 int C = 2; > 224 int K = 3; > 225 long long H = 1LL; > 226 int _ = 14; > 227 END > 228 CASE(3) > 229 int C = 4; > 230 int K = 7; > 231 long long H = 47LL; > 232 int _ = 1008981254; > 233 END > 234 CASE(4) > 235 int C = 4747; > 236 int K = 7; > 237 long long H = 474747474747474747LL; > 238 int _ = 473182063; > 239 END > 240 } > 241 // END CUT HERE
Modified lib/numeric/modArith.cpp from [4e73ce5907de5c44] to [b6522f93bcade295].
3 // Modulo Arithmetics 3 // Modulo Arithmetics 4 // 4 // 5 // Verified by 5 // Verified by 6 // - TCO10 R3 LV3 6 // - TCO10 R3 LV3 7 // - SRM 545 LV2 7 // - SRM 545 LV2 8 //------------------------------------------------------------- 8 //------------------------------------------------------------- 9 9 10 static const int MODVAL = 1000000007; | 10 static const unsigned MODVAL = 1000000007; 11 struct mint 11 struct mint 12 { 12 { 13 int val; | 13 unsigned val; 14 mint():val(0){} 14 mint():val(0){} 15 mint(int x):val(x%MODVAL) {} | 15 mint(int x):val(x%MODVAL) {} 16 mint(size_t x):val(x%MODVAL) {} | 16 mint(unsigned x):val(x%MODVAL) {} 17 mint(LL x):val(x%MODVAL) {} | 17 mint(LL x):val(x%MODVAL) {} 18 }; 18 }; 19 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 19 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 20 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 20 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } 21 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 21 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 22 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } < 23 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } < 24 mint operator+(mint x, mint y) { return x+=y; } 22 mint operator+(mint x, mint y) { return x+=y; } 25 mint operator-(mint x, mint y) { return x-=y; } 23 mint operator-(mint x, mint y) { return x-=y; } 26 mint operator*(mint x, mint y) { return x*=y; } 24 mint operator*(mint x, mint y) { return x*=y; } > 25 > 26 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 27 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } 27 mint operator/(mint x, mint y) { return x/=y; } 28 mint operator/(mint x, mint y) { return x/=y; } > 29 > 30 // nCk :: O(log MODVAL) time, O(n) space. 28 vector<mint> FAC_(1,1); 31 vector<mint> FAC_(1,1); 29 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 32 mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() 30 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } 33 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); } > 34 > 35 // nCk :: O(1) time, O(n^2) space. 31 vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed. | 36 vector< vector<mint> > CP_; 32 mint C(LL n, LL k) { 37 mint C(LL n, LL k) { 33 while( CP_.size() <= n ) { 38 while( CP_.size() <= n ) { 34 int nn = CP_.size(); 39 int nn = CP_.size(); 35 CP_.push_back(vector<mint>(nn+1,1)); 40 CP_.push_back(vector<mint>(nn+1,1)); 36 for(int kk=1; kk<nn; ++kk) 41 for(int kk=1; kk<nn; ++kk) 37 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 42 CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk]; 38 } 43 }