Overview
| SHA1 Hash: | 69a17ebf8a7b9b3809dc64790242941623b7796f |
|---|---|
| Date: | 2021-07-08 13:01:03 |
| User: | kinaba |
| Comment: | TCO21 R3 |
| 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/TCO21-3A-U/1A.cpp version [3986dda3f30c06b9]
> 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 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 mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= > 39 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); } > 40 mint operator/(mint x, mint y) { return x /= y; } > 41 > 42 vector<mint> FAC_(1, 1); > 43 mint FAC(LL n) { while (FAC_.size() <= n) FAC_.push_back(FAC_.back()*LL(FAC_.siz > 44 > 45 // nCk :: O(log MODVAL) time, O(n) space. > 46 mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n - k)); } > 47 > 48 class AnnoyingPasswords { public: > 49 int count(int U, int L, int D) > 50 { > 51 return (solve(-1,U,L,D) * FAC(26) / FAC(26 - U) * FAC(26) / FAC( > 52 } > 53 > 54 int solve(int p, int U, int L, int D) { > 55 tuple<int, int, int, int> key(p, U, L, D); > 56 if (memo.count(key)) > 57 return memo[key]; > 58 if (U == 0 && L == 0 && D == 0) > 59 return 1; > 60 mint ans = 0; > 61 if (p != 0 && U != 0) > 62 ans += solve(0, U - 1, L, D); > 63 if (p != 1 && L != 0) > 64 ans += solve(1, U, L - 1, D); > 65 if (p != 2 && D != 0) > 66 ans += solve(2, U, L, D - 1); > 67 return memo[key] = ans.val; > 68 } > 69 > 70 map<tuple<int, int, int, int>, int> memo; > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const int& Expected, const int& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, AnnoyingPasswords().count(U, L, D));} > 87 int main(){ > 88 > 89 CASE(0) > 90 int U = 4; > 91 int L = 1; > 92 int D = 1; > 93 int _ = 0; > 94 END > 95 CASE(1) > 96 int U = 5; > 97 int L = 0; > 98 int D = 4; > 99 int _ = 783743727; > 100 END > 101 CASE(2) > 102 int U = 1; > 103 int L = 1; > 104 int D = 1; > 105 int _ = 40560; > 106 END > 107 CASE(3) > 108 int U = 2; > 109 int L = 2; > 110 int D = 3; > 111 int _ = 559599923; > 112 END > 113 CASE(4) > 114 int U = 0; > 115 int L = 0; > 116 int D = 0; > 117 int _ = 1; > 118 END > 119 CASE(5) > 120 int U = 26; > 121 int L = 26; > 122 int D = 10; > 123 int _ = 0; > 124 END > 125 CASE(6) > 126 int U = 0; > 127 int L = 0; > 128 int D = 0; > 129 int _ = 1; > 130 END > 131 } > 132 // END CUT HERE
Added SRM/TCO21-3A-U/1B-U.cpp version [a3c837bff36416d6]
> 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 TellBagsApart { public: > 23 string whichBagIsSmaller(vector <int> records) > 24 { > 25 srand(time(0)); > 26 string ans; > 27 for (int i = 0; i < records.size(); i += 8) > 28 ans += char('0' + solve(vector<int>(records.begin() + i, > 29 return ans; > 30 } > 31 > 32 int solve(vector<int> r) { > 33 // same = 3/7, diff = 4/7 > 34 // same = 19/39, diff = 20/39 > 35 int a1 = r[0] + r[1] + r[2] + r[3]; > 36 int s1 = r[0] + r[3]; > 37 int d1 = a1 - s1; > 38 int a2 = r[4] + r[5] + r[6] + r[7]; > 39 int s2 = r[4] + r[7]; > 40 int d2 = a2 - s2; > 41 int lhs, rhs; > 42 if (a1 == 0) { > 43 // s2/a2 closer to 19/39 ? 1 : 2 > 44 // 125/273 < s2/a2 > 45 lhs = 125 * a2; > 46 rhs = s2 * 273; > 47 } > 48 else if (a2 == 0) { > 49 // s1/a1 closer to 3/7 ? 1 : 2 > 50 // s1/a1 < 125/273 > 51 lhs = s1 * 273; > 52 rhs = 125 * a1; > 53 } > 54 else { > 55 // s1/a1 < s2/a2 ? 1 : 2 > 56 lhs = s1 * a2; > 57 rhs = s2 * a1; > 58 } > 59 > 60 if (lhs == rhs) { > 61 return (rand() >> 8) & 1 ? 1 : 2; > 62 } > 63 else { > 64 return lhs < rhs ? 1 : 2; > 65 } > 66 } > 67 }; > 68 > 69 // BEGIN CUT HERE > 70 #include <ctime> > 71 double start_time; string timer() > 72 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 73 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 74 { os << "{ "; > 75 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 76 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 77 void verify_case(const string& Expected, const string& Received) { > 78 bool ok = (Expected == Received); > 79 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 80 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 81 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 82 #define END verify_case(_, TellBagsApart().whichBagIsSmaller(records));} > 83 int main(){ > 84 > 85 CASE(0) > 86 int records_[] = {262, 371, 340, 277, 303, 304, 333, 310, > 87 296, 326, 370, 275, 312, 329, 284, 308, > 88 265, 402, 372, 279, 279, 317, 307, 279, > 89 112, 160, 121, 102, 497, 497, 505, 506}; > 90 vector <int> records(records_, records_+sizeof(records_)/sizeof(*recor > 91 string _ = "1111"; > 92 END > 93 CASE(1) > 94 int records_[] = {401, 405, 345, 358, 203, 295, 284, 209, > 95 348, 380, 396, 361, 221, 274, 307, 213, > 96 361, 347, 410, 347, 246, 287, 298, 204, > 97 301, 389, 412, 304, 253, 289, 280, 272, > 98 303, 450, 388, 290, 270, 286, 246, 267, > 99 328, 354, 326, 362, 254, 305, 309, 262, > 100 290, 362, 391, 296, 285, 282, 313, 281, > 101 338, 335, 345, 335, 220, 338, 335, 254, > 102 309, 356, 348, 323, 239, 344, 343, 238, > 103 264, 368, 365, 258, 301, 312, 328, 304, > 104 256, 368, 343, 295, 296, 323, 319, 300, > 105 275, 318, 383, 258, 320, 340, 306, 300, > 106 275, 301, 323, 309, 273, 372, 366, 281, > 107 263, 331, 290, 309, 277, 358, 395, 277, > 108 261, 310, 291, 259, 301, 407, 379, 292, > 109 256, 318, 297, 257, 325, 358, 366, 323, > 110 284, 287, 274, 286, 294, 406, 358, 311, > 111 266, 271, 282, 256, 282, 395, 429, 319, > 112 270, 274, 278, 268, 308, 396, 404, 302, > 113 203, 283, 299, 229, 368, 401, 377, 340}; > 114 vector <int> records(records_, records_+sizeof(records_)/sizeof(*recor > 115 string _ = "22211212211122212221"; > 116 END > 117 /* > 118 CASE(2) > 119 int records_[] = ; > 120 vector <int> records(records_, records_+sizeof(records_)/sizeof(*recor > 121 string _ = ; > 122 END > 123 CASE(3) > 124 int records_[] = ; > 125 vector <int> records(records_, records_+sizeof(records_)/sizeof(*recor > 126 string _ = ; > 127 END > 128 */ > 129 } > 130 // END CUT HERE
Added SRM/TCO21-3A-U/1C-U.cpp version [556c57b27a57d85a]
> 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 TowerPlacement { public: > 23 int solve(int R, int C, int seed, int X) > 24 { > 25 vector<int> qr(50000), qc(50000); > 26 LL state = seed; > 27 for (int i = 0; i < 50000; ++i) { > 28 state = (state * 1103515245 + 12345) & 0x7fffffffLL; > 29 qr[i] = (state / 1000) % R; > 30 state = (state * 1103515245 + 12345) & 0x7fffffffLL; > 31 qc[i] = (state / 1000) % C; > 32 } > 33 > 34 vector<bool> rej(50000); > 35 for (int r = 0; r < X; ++r) { > 36 int L = 0, R = 50001; > 37 while (R - L > 1) { > 38 int M = (L + R) / 2; > 39 (feasible(R,C,qr,qc,rej,M) ? L : R) = M; > 40 } > 41 if (L == 50000) > 42 return -1; > 43 if (r == X - 1) > 44 return L; > 45 rej[L] = true; > 46 } > 47 } > 48 > 49 // Is placing [0, M) feasible? > 50 bool feasible(int R, int C, const vector<int>& qr, const vector<int>& qc > 51 #define ENC(r,c) ((r)*C+(c)) > 52 map<int, int> t; > 53 for (int i = 0; i < M; ++i) { > 54 if (rej[i]) > 55 continue; > 56 int key = ENC(qr[i], qc[i]); > 57 if (t.count(key)) > 58 continue; > 59 > 60 t[key] = i; > 61 > 62 // conflict generation > 63 qr[i]+1, qc[i] > 64 } > 65 // solve > 66 return false; > 67 #undef ENC > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const int& Expected, const int& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, TowerPlacement().solve(R, C, seed, X));} > 85 int main(){ > 86 > 87 CASE(0) > 88 int R = 1; > 89 int C = 1; > 90 int seed = 47; > 91 int X = 5; > 92 int _ = 4; > 93 END > 94 CASE(1) > 95 int R = 3; > 96 int C = 3; > 97 int seed = 47; > 98 int X = 4; > 99 int _ = 6; > 100 END > 101 CASE(2) > 102 int R = 10000; > 103 int C = 14700; > 104 int seed = 12345; > 105 int X = 1; > 106 int _ = -1; > 107 END > 108 CASE(3) > 109 int R = 10; > 110 int C = 12; > 111 int seed = 123456789; > 112 int X = 3; > 113 int _ = 19; > 114 END > 115 /* > 116 CASE(4) > 117 int R = ; > 118 int C = ; > 119 int seed = ; > 120 int X = ; > 121 int _ = ; > 122 END > 123 CASE(5) > 124 int R = ; > 125 int C = ; > 126 int seed = ; > 127 int X = ; > 128 int _ = ; > 129 END > 130 */ > 131 } > 132 // END CUT HERE