Overview
| SHA1 Hash: | 76db68d6341a07dcfd40826b81e032c0069fddd3 |
|---|---|
| Date: | 2018-07-28 17:47:09 |
| User: | kinaba |
| Comment: | TCO18R3B & 4 |
| 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/TCO18-3B-U/1A.cpp version [51d9cbf8cbd55630]
> 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 SquareCutout { public: > 23 int verify(vector <string> cutout) > 24 { > 25 const int Y = cutout.size(), X = cutout[0].size(); > 26 > 27 bool has_black = false; > 28 for (int y = 0; y < Y; ++y) > 29 for (int x = 0; x < X; ++x) > 30 if (cutout[y][x] == '#') > 31 has_black = true; > 32 if (!has_black) > 33 return 1; > 34 > 35 int ym = Y, xm = X, yM = 0, xM = 0; > 36 for (int y = 0; y < Y; ++y) > 37 for (int x = 0; x < X; ++x) > 38 if (cutout[y][x] == '#') > 39 ym = min(ym, y), yM = max(yM, y), xm = m > 40 > 41 for (int y = ym; y <= yM; ++y) > 42 for (int x = xm; x <= xM; ++x) > 43 if (cutout[y][x] != '#') > 44 return 0; > 45 > 46 bool x_extendable = (xm == 0 || xM == X - 1); > 47 bool y_extendable = (ym == 0 || yM == Y - 1); > 48 int yy = yM - ym + 1; > 49 int xx = xM - xm + 1; > 50 if (yy == xx) > 51 return yy; > 52 if (yy < xx) > 53 return y_extendable ? xx : 0; > 54 return x_extendable ? yy : 0; > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const int& Expected, const int& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, SquareCutout().verify(cutout));} > 72 int main(){ > 73 > 74 CASE(0) > 75 string cutout_[] = {".....", > 76 "..##.", > 77 "..##.", > 78 ".....", > 79 "....."}; > 80 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 81 int _ = 2; > 82 END > 83 CASE(1) > 84 string cutout_[] = {"...", > 85 "..."}; > 86 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 87 int _ = 1; > 88 END > 89 CASE(2) > 90 string cutout_[] = {".....", > 91 ".###.", > 92 ".#.#.", > 93 ".###.", > 94 "....."}; > 95 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 96 int _ = 0; > 97 END > 98 CASE(3) > 99 string cutout_[] = {"..####", > 100 "..####", > 101 "......"}; > 102 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 103 int _ = 4; > 104 END > 105 CASE(4) > 106 string cutout_[] = {"..#..", > 107 ".###.", > 108 "#####", > 109 ".###.", > 110 "..#.."}; > 111 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 112 int _ = 0; > 113 END > 114 CASE(5) > 115 string cutout_[] = { "...", "...", "..." }; > 116 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 117 int _ = 1; > 118 END > 119 /* > 120 CASE(6) > 121 string cutout_[] = ; > 122 vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout > 123 int _ = ; > 124 END > 125 */ > 126 } > 127 // END CUT HERE
Added SRM/TCO18-3B-U/1B.cpp version [48b50023e1108913]
> 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 TestProctoring { public: > 23 double expectedTime(vector <int> p, vector <int> q) > 24 { > 25 const int N = p.size(); > 26 vector<double> dp(1<<N), dp2((N+1)*(1<<N)); > 27 for (int mask = 1; mask < (1<<N); ++mask) { > 28 for (int i = N; i >= 0; --i) > 29 if (i == N) > 30 dp2[(i << N) | mask] = dp[mask]; > 31 else if ((mask&(1 << i)) == 0) > 32 dp2[(i << N) | mask] = dp2[((i + 1) << N > 33 else { > 34 double e1 = dp2[((i + 1) << N) | mask &~ > 35 double e2 = dp2[((i + 1) << N) | mask]; > 36 dp2[(i << N) | mask] = (p[i] * e1 + (q[i > 37 } > 38 > 39 double pp = 1.0; > 40 for (int i = 0; i<N; ++i) if (mask&(1 << i)) > 41 pp = pp * (q[i] - p[i]) / q[i]; > 42 dp[mask] = (dp2[mask]+1) / (1 - pp); > 43 > 44 // Rerun > 45 for (int i = N; i >= 0; --i) > 46 if (i == N) > 47 dp2[(i << N) | mask] = dp[mask]; > 48 else if ((mask&(1 << i)) == 0) > 49 dp2[(i << N) | mask] = dp2[((i + 1) << N > 50 else { > 51 double e1 = dp2[((i + 1) << N) | mask &~ > 52 double e2 = dp2[((i + 1) << N) | mask]; > 53 dp2[(i << N) | mask] = (p[i] * e1 + (q[i > 54 } > 55 } > 56 > 57 return dp[(1<<N) - 1]; > 58 } > 59 }; > 60 > 61 // BEGIN CUT HERE > 62 #include <ctime> > 63 double start_time; string timer() > 64 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 65 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 66 { os << "{ "; > 67 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 68 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 69 void verify_case(const double& Expected, const double& Received) { > 70 bool ok = (abs(Expected - Received)/abs(Expected) < 1e-6); > 71 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 73 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 74 #define END verify_case(_, TestProctoring().expectedTime(p, q));} > 75 int main(){ > 76 CASE(0) > 77 int p_[] = {2}; > 78 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 79 int q_[] = {4}; > 80 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 81 double _ = 2.0; > 82 END > 83 CASE(1) > 84 int p_[] = {1,2}; > 85 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 86 int q_[] = {2,4}; > 87 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 88 double _ = 2.6666666666666665; > 89 END > 90 CASE(2) > 91 int p_[] = {3,1,2,4,2,5}; > 92 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 93 int q_[] = {3,1,2,4,2,5}; > 94 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 95 double _ = 1.0; > 96 END > 97 CASE(3) > 98 int p_[] = {1,1,1,1,1,1,1,1}; > 99 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 100 int q_[] = {1,2,3,4,5,6,7,8}; > 101 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 102 double _ = 13.604834665120991; > 103 END > 104 CASE(4) > 105 int p_[] = {2,3,5,7,11,13,17}; > 106 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 107 int q_[] = {3,5,7,11,13,17,19}; > 108 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 109 double _ = 2.6299445065924276; > 110 END > 111 CASE(5) > 112 int p_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; > 113 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 114 int q_[] = {1000000000,1000000000,1000000000,1000000000,1000000000, > 115 1000000000,1000000000,1000000000,1000000000,1000000000, > 116 1000000000,1000000000,1000000000,1000000000,1000000000, > 117 1000000000,1000000000,1000000000,1000000000,1000000000}; > 118 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 119 double _ = 3.597740924491638E9; > 120 END > 121 /* > 122 CASE(6) > 123 int p_[] = ; > 124 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 125 int q_[] = ; > 126 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 127 double _ = ; > 128 END > 129 CASE(7) > 130 int p_[] = ; > 131 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 132 int q_[] = ; > 133 vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); > 134 double _ = ; > 135 END > 136 */ > 137 } > 138 // END CUT HERE
Added SRM/TCO18-4-U/1A.cpp version [80f635d2b3ec8a20]
> 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 > 24 template<typename T> > 25 struct DP2 > 26 { > 27 const int N1, N2; > 28 vector<T> data; > 29 DP2(int N1, int N2, const T& t = T()) > 30 : N1(N1), N2(N2), data(N1*N2, t) { > 31 assert(data.size() * sizeof(T)<(1 << 28)); > 32 } > 33 T& operator()(int i1, int i2) > 34 { > 35 return data[(i1*N2) + i2]; > 36 } > 37 void swap(DP2& rhs) > 38 { > 39 data.swap(rhs.data); > 40 } > 41 }; > 42 > 43 class SumPyramid { public: > 44 int countPyramids(int levels, int top) > 45 { > 46 vector<int> C(1, 1); > 47 for (int _ = 1; _ < levels; ++_) { > 48 vector<int> CC(C.size() + 1); > 49 for (size_t i = 0; i < CC.size(); ++i) > 50 CC[i] = min(top + 1, (i ? C[i - 1] : 0) + (i<C.s > 51 C = CC; > 52 } > 53 > 54 DP2<int> memo(levels, top+1, -1); > 55 return rec(levels - 1, 0, top, C, memo); > 56 } > 57 > 58 int rec(int n, int k, int sum, const vector<int>& C, DP2<int>& memo) > 59 { > 60 // #{x,y,..,z} where nCk x + nC{k+1} y + ... + nCn z == sum > 61 if (memo(k, sum) != -1) > 62 return memo(k, sum); > 63 > 64 if (k == n) > 65 return memo(k, sum) = 1; > 66 int ans = 0; > 67 for (int v = 0; v*C[k] <= sum; ++v) > 68 ans = (ans + rec(n, k+1, sum - v*C[k], C, memo)) % MODVA > 69 return memo(k, sum) = ans; > 70 } > 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(_, SumPyramid().countPyramids(levels, top));} > 87 int main(){ > 88 > 89 CASE(0) > 90 int levels = 1; > 91 int top = 47; > 92 int _ = 1; > 93 END > 94 CASE(1) > 95 int levels = 2; > 96 int top = 10; > 97 int _ = 11; > 98 END > 99 CASE(2) > 100 int levels = 3; > 101 int top = 2; > 102 int _ = 4; > 103 END > 104 CASE(3) > 105 int levels = 5; > 106 int top = 7; > 107 int _ = 18; > 108 END > 109 CASE(4) > 110 int levels = 1000; > 111 int top = 1000; > 112 int _ = -1; > 113 END > 114 /* > 115 CASE(5) > 116 int levels = ; > 117 int top = ; > 118 int _ = ; > 119 END > 120 */ > 121 } > 122 // END CUT HERE
Added SRM/TCO18-4-U/1B-U.cpp version [86534a42ab0996e3]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <unordered_map> > 8 #include <set> > 9 #include <algorithm> > 10 #include <numeric> > 11 #include <iterator> > 12 #include <functional> > 13 #include <complex> > 14 #include <queue> > 15 #include <stack> > 16 #include <cmath> > 17 #include <cassert> > 18 #include <tuple> > 19 using namespace std; > 20 typedef long long LL; > 21 typedef complex<double> CMP; > 22 > 23 class PolylineAreas { public: > 24 vector<long long> findAreas(string polyline) > 25 { > 26 string cmd; > 27 { > 28 const char* p = polyline.c_str(); > 29 while (*p) > 30 parse_one(p, cmd); > 31 } > 32 > 33 #define enc(x,y) ((LL(x+1000000)<<32)|(y+1000000)) > 34 const int dx[] = { 1, 0, -1, 0 }; > 35 const int dy[] = { 0, 1, 0, -1 }; > 36 > 37 unordered_map<LL, int> edge; > 38 { > 39 int x = 0, y = 0, d = 0; > 40 for (int ch : cmd) { > 41 switch (ch) { > 42 case 'F': { > 43 LL p = enc(x, y); > 44 x += dx[d]; > 45 y += dy[d]; > 46 LL c = enc(x, y); > 47 edge[p] |= 1 << d; > 48 edge[c] |= 1 << ((d + 2) % 4); > 49 > 50 break; > 51 } > 52 case 'L': d = (d + 1) % 4; break; > 53 case 'R': d = (d + 3) % 4; break; > 54 } > 55 } > 56 } > 57 > 58 vector<LL> ans; > 59 { > 60 for (auto pd : edge) { > 61 const int s_x = int(pd.first >> 32) - 1000000; > 62 const int s_y = int(pd.first & 0xffffffff) - 100 > 63 int& ds = pd.second; > 64 for (int d = 0; d < 4; ++d) if (ds&(1 << d)) { > 65 // go clockwise from (x,y) -> d > 66 > 67 LL area = 0; > 68 int x = s_x, y = s_y; > 69 do { > 70 //cerr << "(" << x << "," << y < > 71 > 72 // move > 73 int px = x, py = y; > 74 x += dx[d]; > 75 y += dy[d]; > 76 edge[enc(px, py)] &= ~(1 << d); > 77 > 78 // turn > 79 int& dd = edge[enc(x, y)]; > 80 if (dd & (1 << ((d + 3) % 4))) > 81 d = (d + 3) % 4; > 82 else if (dd & (1 << d)) > 83 ; > 84 else if (dd & (1 << ((d + 1) % 4 > 85 d = (d + 1) % 4; > 86 else if (dd & (1 << ((d + 2)%4)) > 87 d = (d + 2) % 4; > 88 else > 89 break; > 90 > 91 // calc area > 92 area += LL(x - s_x)*(py - s_y) - > 93 //cerr << LL(x - s_x)*(py - s_y) > 94 } while (x != s_x || y != s_y); > 95 > 96 if(x==s_x && y==s_y && area > 0) > 97 ans.push_back(area/2); > 98 } > 99 } > 100 } > 101 > 102 sort(ans.begin(), ans.end()); > 103 if (ans.size() > 200) { > 104 vector<LL> a2(ans.begin(), ans.begin() + 100); > 105 a2.insert(a2.end(), ans.end() - 100, ans.end()); > 106 return a2; > 107 } > 108 return ans; > 109 } > 110 > 111 void parse_one(const char*& p, string& buf) { > 112 if ('0' <= *p && *p <= '9') { > 113 int rep = (*p++ - '0'); > 114 while('0' <= *p && *p <= '9') > 115 rep = rep*10 + (*p++ - '0'); > 116 > 117 string sub; > 118 parse_one(p, sub); > 119 while (rep-- > 0) > 120 buf += sub; > 121 } > 122 else if (*p == '[') { > 123 for (++p; *p != ']'; ) > 124 parse_one(p, buf); > 125 ++p; > 126 } > 127 else { > 128 buf += *p++; > 129 } > 130 } > 131 }; > 132 > 133 // BEGIN CUT HERE > 134 #include <ctime> > 135 double start_time; string timer() > 136 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 137 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 138 { os << "{ "; > 139 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 140 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 141 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 142 bool ok = (Expected == Received); > 143 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 144 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 145 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 146 #define END verify_case(_, PolylineAreas().findAreas(polyline));} > 147 int main(){ > 148 CASE(0) > 149 string polyline = "FRFLF"; > 150 vector<long long> _; > 151 END > 152 CASE(1) > 153 string polyline = "4[100FR]"; > 154 long long __[] = {10000 }; > 155 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 156 END > 157 CASE(2) > 158 string polyline = "2[2[100FR]]"; > 159 long long __[] = {10000 }; > 160 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 161 END > 162 CASE(3) > 163 string polyline = "47[100FR]"; > 164 long long __[] = {10000 }; > 165 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 166 END > 167 CASE(4) > 168 string polyline = "1000000[]"; > 169 vector<long long> _; > 170 END > 171 CASE(5) > 172 string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL6F"; > 173 long long __[] = {1, 2, 2, 3, 3, 4, 6, 6, 9 }; > 174 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 175 END > 176 CASE(6) > 177 string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL4F"; > 178 long long __[] = {1, 2, 2, 3, 3, 4, 6, 15 }; > 179 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 180 END > 181 CASE(7) > 182 string polyline = "3FRFRFLFLFRFR3FRFRFLFLFRF"; > 183 long long __[] = {7 }; > 184 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 185 END > 186 CASE(8) > 187 string polyline = "250000F"; > 188 long long __[] = {-1}; > 189 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 190 END > 191 /* > 192 CASE(9) > 193 string polyline = ; > 194 long long __[] = ; > 195 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 196 END > 197 */ > 198 } > 199 // END CUT HERE