Overview
| SHA1 Hash: | 8cbd8685a83ce946ebbe1ee65d9659ca88a936c9 |
|---|---|
| Date: | 2019-07-19 04:27:01 |
| User: | kinaba |
| Comment: | TCO193B |
| 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/TCO19-3B-U/1A.cpp version [710858e8febd2397]
> 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 TwoLadders { public: > 23 long long minSteps(int sx, int lx1, int lx2, vector <int> X, vector <int > 24 { > 25 map<int, vector<int>> y2x; > 26 for (int i = 0; i < X.size(); ++i) > 27 y2x[Y[i]].push_back(X[i]); > 28 > 29 map<int, pair<int, int>> y2mM; > 30 for (auto kv : y2x) > 31 y2mM[kv.first] = make_pair( > 32 *min_element(kv.second.begin(), kv.second.end()) > 33 *max_element(kv.second.begin(), kv.second.end()) > 34 ); > 35 > 36 auto cur = y2mM.begin(); > 37 > 38 // best 2 move candidates in the prvious level > 39 int p1 = sx; > 40 int p2 = sx; > 41 LL b1 = 0; > 42 LL b2 = 0; > 43 int yy = 0; > 44 > 45 if(cur->first == 0) { > 46 int m = cur->second.first; > 47 int M = cur->second.second; > 48 ++cur; > 49 p1 = m; > 50 b1 = abs(sx - M) + abs(M - m); > 51 p2 = M; > 52 b2 = abs(sx - m) + abs(M - m); > 53 } > 54 > 55 for (; cur != y2mM.end(); ++cur) { > 56 int ydiff = cur->first - yy; > 57 yy = cur->first; > 58 int m = cur->second.first; > 59 int M = cur->second.second; > 60 > 61 int prev_p1 = p1; > 62 int prev_p2 = p2; > 63 LL prev_b1 = b1; > 64 LL prev_b2 = b2; > 65 > 66 p1 = m; > 67 b1 = min({ > 68 prev_b1 + ydiff + abs(prev_p1 - lx1) + abs(lx1 - > 69 prev_b1 + ydiff + abs(prev_p1 - lx2) + abs(lx2 - > 70 prev_b2 + ydiff + abs(prev_p2 - lx1) + abs(lx1 - > 71 prev_b2 + ydiff + abs(prev_p2 - lx2) + abs(lx2 - > 72 }); > 73 p2 = M; > 74 b2 = min({ > 75 prev_b1 + ydiff + abs(prev_p1 - lx1) + abs(lx1 - > 76 prev_b1 + ydiff + abs(prev_p1 - lx2) + abs(lx2 - > 77 prev_b2 + ydiff + abs(prev_p2 - lx1) + abs(lx1 - > 78 prev_b2 + ydiff + abs(prev_p2 - lx2) + abs(lx2 - > 79 }); > 80 } > 81 return min(b1, b2); > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const long long& Expected, const long long& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, TwoLadders().minSteps(sx, lx1, lx2, X, Y));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int sx = 10; > 103 int lx1 = 0; > 104 int lx2 = 100; > 105 int X_[] = {47, 42}; > 106 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 107 int Y_[] = {0, 0}; > 108 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 109 long long _ = 37LL; > 110 END > 111 CASE(1) > 112 int sx = 10; > 113 int lx1 = 8; > 114 int lx2 = 11; > 115 int X_[] = {10, 12}; > 116 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 117 int Y_[] = {1, 1}; > 118 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 119 long long _ = 5LL; > 120 END > 121 CASE(2) > 122 int sx = 10; > 123 int lx1 = 8; > 124 int lx2 = 42; > 125 int X_[] = {10, 12}; > 126 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 127 int Y_[] = {1, 1}; > 128 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 129 long long _ = 7LL; > 130 END > 131 CASE(3) > 132 int sx = 10; > 133 int lx1 = 8; > 134 int lx2 = 42; > 135 int X_[] = {10, 100, 12}; > 136 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 137 int Y_[] = {1, 0, 1}; > 138 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 139 long long _ = 181LL; > 140 END > 141 CASE(4) > 142 int sx = 500000000; > 143 int lx1 = 1; > 144 int lx2 = 999999999; > 145 int X_[] = {0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, > 146 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 147 int Y_[] = {1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 999999947, 999999947, 90000004 > 148 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 149 long long _ = 8499999959LL; > 150 END > 151 /* > 152 CASE(5) > 153 int sx = ; > 154 int lx1 = ; > 155 int lx2 = ; > 156 int X_[] = ; > 157 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 158 int Y_[] = ; > 159 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 160 long long _ = LL; > 161 END > 162 CASE(6) > 163 int sx = ; > 164 int lx1 = ; > 165 int lx2 = ; > 166 int X_[] = ; > 167 vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_)); > 168 int Y_[] = ; > 169 vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_)); > 170 long long _ = LL; > 171 END > 172 */ > 173 } > 174 // END CUT HERE
Added SRM/TCO19-3B-U/1B.cpp version [70b57b6d4d4ca3f0]
> 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 PrefixComposite { public: > 23 vector<long long> minMax(long long A, long long B) > 24 { > 25 LL r = solve(B); > 26 if (r < A) > 27 return vector<LL>(); > 28 > 29 LL L = A - 1, R = r; > 30 while(R-L>1) { > 31 LL C = (L + R) / 2; > 32 LL c = solve(C); > 33 if (c < A) > 34 L = C; > 35 else > 36 R = c; > 37 } > 38 return vector<LL>({ R, r }); > 39 } > 40 > 41 // max such value <= B > 42 LL solve(LL B) { > 43 vector<int> bb; > 44 for(; B!=0; B/=10) > 45 bb.push_back(B % 10); > 46 reverse(bb.begin(), bb.end()); > 47 > 48 function<LL(LL, int)> rec = [&](LL pref, int i) { > 49 if (i == bb.size()) > 50 return pref; > 51 > 52 LL pp = pref * 10 + bb[i]; > 53 if(is_composite(pp)) { > 54 LL r = rec(pp, i + 1); > 55 if (r) > 56 return r; > 57 } > 58 > 59 for (int k = bb[i] - 1; k >= 0; --k) { > 60 LL pp = pref * 10 + k; > 61 if (is_composite(pp)) { > 62 int n = bb.size() - i - 1; > 63 // get max from pp ++ [0-9]*n > 64 for (int j = 0; j < n; ++j) > 65 if (is_composite(pp*10+9)) > 66 pp = pp*10+9; > 67 else > 68 pp = pp*10+8; > 69 return pp; > 70 } > 71 } > 72 return 0LL; > 73 }; > 74 return rec(0, 0); > 75 } > 76 > 77 bool is_composite(LL v) > 78 { > 79 if (v == 0) > 80 return true; > 81 for (LL p = 2; p*p <= v; ++p) > 82 if (v%p == 0) > 83 return true; > 84 return false; > 85 } > 86 }; > 87 > 88 // BEGIN CUT HERE > 89 #include <ctime> > 90 double start_time; string timer() > 91 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 92 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 93 { os << "{ "; > 94 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 95 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 96 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 97 bool ok = (Expected == Received); > 98 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 99 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 100 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 101 #define END verify_case(_, PrefixComposite().minMax(A, B));} > 102 int main(){ > 103 > 104 CASE(0) > 105 long long A = 1LL; > 106 long long B = 3LL; > 107 vector<long long> _; > 108 END > 109 CASE(1) > 110 long long A = 1LL; > 111 long long B = 4LL; > 112 long long __[] = {4, 4 }; > 113 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 114 END > 115 CASE(2) > 116 long long A = 123LL; > 117 long long B = 838LL; > 118 long long __[] = {400, 828 }; > 119 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 120 END > 121 CASE(3) > 122 long long A = 409LL; > 123 long long B = 87343LL; > 124 long long __[] = {420, 87343 }; > 125 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 126 END > 127 CASE(4) > 128 long long A = 979797LL; > 129 long long B = 979898LL; > 130 vector<long long> _; > 131 END > 132 CASE(5) > 133 long long A = 600LL; > 134 long long B = 703LL; > 135 long long __[] = {600, 699 }; > 136 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 137 END > 138 CASE(6) > 139 long long A = 1LL; > 140 long long B = 100000000000LL; > 141 long long __[] = {4, 99999999999 }; > 142 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 143 END > 144 CASE(7) > 145 long long A = 37337999LL; > 146 long long B = 37337999LL; > 147 vector<long long> _; > 148 END > 149 CASE(8) > 150 long long A = 22LL; > 151 long long B = 39LL; > 152 vector<long long> _; > 153 END > 154 CASE(9) > 155 long long A = 600LL; > 156 long long B = 699LL; > 157 long long __[] = { 600, 699 }; > 158 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 159 END > 160 CASE(10) > 161 long long A = 1LL; > 162 long long B = 1LL; > 163 vector<long long> _; > 164 END > 165 CASE(10) > 166 long long A = 1LL; > 167 long long B = 6LL; > 168 vector<long long> _; > 169 END > 170 } > 171 // END CUT HERE
Added SRM/TCO19-3B-U/1C-U.cpp version [4aebde82e204f3cf]
> 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 mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= > 38 mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); } > 39 mint operator/(mint x, mint y) { return x /= y; } > 40 > 41 class DiagonalColumn { public: > 42 int countGrids(int H, int W) > 43 { > 44 mint ans = 1; // all black > 45 for(int l=0; l<W; ++l) > 46 for (int r = 0; l + r < W; ++r) { > 47 if (W - l - r <= 2) > 48 ans += 1; > 49 else > 50 ans += sub(H, W - l - r); > 51 } > 52 return ans.val; > 53 } > 54 > 55 mint sub(LL H, LL W) > 56 { > 57 // columns = _?????_ > 58 mint f = POW(2, W - 2); > 59 > 60 // Diag: H+W-1個のうち > 61 // 最初H個のどれかはmust空き > 62 // 最後H個のどれかはmust空き > 63 // 他でH連続塗りがある場合は縦の自由度が減る /2 > 64 vector<mint> dp(H+1); > 65 dp[0] = f; > 66 for (int i = 0; i < H + W - 1; ++i) { > 67 vector<mint> dp_prev = dp; > 68 vector<mint> dp(H+1); > 69 for (int r = 0; r <= H; ++r) { > 70 if (r == 0) { > 71 accumulate(dp_prev.begin(), dp_prev.end( > 72 } > 73 else { > 74 if(r == H) > 75 dp[r] = (i == H - 1 || i == H + > 76 else > 77 dp[r] = dp_prev[r - 1]; > 78 } > 79 } > 80 } > 81 return accumulate(dp.begin(), dp.begin() + H, mint(0)); > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const int& Expected, const int& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, DiagonalColumn().countGrids(H, W));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int H = 2; > 103 int W = 2; > 104 int _ = 12; > 105 END > 106 CASE(1) > 107 int H = 2; > 108 int W = 3; > 109 int _ = 37; > 110 END > 111 CASE(2) > 112 int H = 3; > 113 int W = 2; > 114 int _ = 28; > 115 END > 116 CASE(3) > 117 int H = 1; > 118 int W = 5; > 119 int _ = 32; > 120 END > 121 CASE(4) > 122 int H = 6; > 123 int W = 1; > 124 int _ = 64; > 125 END > 126 CASE(5) > 127 int H = 38; > 128 int W = 38; > 129 int _ = 173889321; > 130 END > 131 /* > 132 CASE(6) > 133 int H = ; > 134 int W = ; > 135 int _ = ; > 136 END > 137 CASE(7) > 138 int H = ; > 139 int W = ; > 140 int _ = ; > 141 END > 142 */ > 143 } > 144 // END CUT HERE