Overview
| SHA1 Hash: | 5fed235c32ed7b1c8c8730a35019f522cb478d92 |
|---|---|
| Date: | 2020-09-10 13:21:55 |
| User: | kinaba |
| Comment: | TCO203B |
| 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/TCO20-3B-U/1A.cpp version [56c161848bbee859]
> 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 VisitALot { public: > 23 string travel(int R, int C, vector <int> obsr, vector <int> obsc) > 24 { > 25 if (R >= 6) { > 26 string ans; > 27 int r = 0, c = 0; > 28 while (r < R) { > 29 if (count(obsr.begin(), obsr.end(), r) == 0) { > 30 if (c == 0) > 31 while (c + 1 < C) { > 32 ans += 'E'; > 33 c++; > 34 } > 35 else > 36 while (c - 1 >= 0) { > 37 ans += 'W'; > 38 c--; > 39 } > 40 } > 41 > 42 if (r + 1 < R) > 43 ans += 'S'; > 44 r++; > 45 } > 46 return ans; > 47 } > 48 > 49 if (C >= 6) { > 50 string ans; > 51 int r = 0, c = 0; > 52 while (c < C) { > 53 if (count(obsc.begin(), obsc.end(), c) == 0) { > 54 if (r == 0) > 55 while (r + 1 < R) { > 56 ans += 'S'; > 57 r++; > 58 } > 59 else > 60 while (r - 1 >= 0) { > 61 ans += 'N'; > 62 r--; > 63 } > 64 } > 65 > 66 if (c + 1 < C) > 67 ans += 'E'; > 68 c++; > 69 } > 70 return ans; > 71 } > 72 > 73 // naive search > 74 vector<vector<bool>> visited(R, vector<bool>(C)); > 75 for (int i = 0; i < obsr.size(); ++i) > 76 visited[obsr[i]][obsc[i]] = true; > 77 visited[0][0] = true; > 78 string ans; > 79 dfs(ans, R, C, 0, 0, visited); > 80 return ans; > 81 } > 82 > 83 bool dfs(string& s, int R, int C, int r, int c, vector<vector<bool>>& vi > 84 int dr[] = { -1,+1,0,0 }; > 85 int dc[] = { 0,0,-1,+1 }; > 86 char dd[] = { 'N', 'S', 'W', 'E' }; > 87 for (int i = 0; i < 4; ++i) { > 88 int rr = r + dr[i]; > 89 int cc = c + dc[i]; > 90 if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[r > 91 visited[rr][cc] = true; > 92 s += dd[i]; > 93 if (s.size()+1 >= (R*C+1)/2 || dfs(s, R, C, rr, > 94 return true; > 95 s.resize(s.size() - 1); > 96 visited[rr][cc] = false; > 97 } > 98 } > 99 return false; > 100 } > 101 }; > 102 > 103 // BEGIN CUT HERE > 104 #include <ctime> > 105 double start_time; string timer() > 106 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 107 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 108 { os << "{ "; > 109 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 110 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 111 void verify_case(const string& Expected, const string& Received) { > 112 bool ok = (Expected == Received); > 113 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 114 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 115 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 116 #define END verify_case(_, VisitALot().travel(R, C, obsr, obsc));} > 117 int main(){ > 118 > 119 CASE(0) > 120 int R = 2; > 121 int C = 3; > 122 vector <int> obsr; > 123 vector <int> obsc; > 124 string _ = "SENE"; > 125 END > 126 CASE(1) > 127 int R = 6; > 128 int C = 5; > 129 int obsr_[] = {1, 1, 4}; > 130 vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_)); > 131 int obsc_[] = {1, 3, 1}; > 132 vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_)); > 133 string _ = "SSEESWWSSEENEE"; > 134 END > 135 CASE(2) > 136 int R = 7; > 137 int C = 8; > 138 vector <int> obsr; > 139 vector <int> obsc; > 140 string _ = "EEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEESWWWWWWWSEEEEEEE"; > 141 END > 142 CASE(3) > 143 int R = 7; > 144 int C = 4; > 145 int obsr_[] = { 5,2,1 }; > 146 vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_)); > 147 int obsc_[] = { 1,2,2 }; > 148 vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_)); > 149 string _ = "?"; > 150 END > 151 CASE(4) > 152 int R = 50; > 153 int C = 50; > 154 int obsr_[] = { 1,10,15 }; > 155 vector <int> obsr(obsr_, obsr_+sizeof(obsr_)/sizeof(*obsr_)); > 156 int obsc_[] = { 28, 17, 3 }; > 157 vector <int> obsc(obsc_, obsc_+sizeof(obsc_)/sizeof(*obsc_)); > 158 string _ = "?"; > 159 END > 160 CASE(4) > 161 int R = 5; > 162 int C = 5; > 163 int obsr_[] = { 1,2,3 }; > 164 vector <int> obsr(obsr_, obsr_ + sizeof(obsr_) / sizeof(*obsr_)); > 165 int obsc_[] = { 1,2,3 }; > 166 vector <int> obsc(obsc_, obsc_ + sizeof(obsc_) / sizeof(*obsc_)); > 167 string _ = "?"; > 168 END > 169 CASE(4) > 170 int R = 4; > 171 int C = 4; > 172 int obsr_[] = { 1,2 }; > 173 vector <int> obsr(obsr_, obsr_ + sizeof(obsr_) / sizeof(*obsr_)); > 174 int obsc_[] = { 1,2 }; > 175 vector <int> obsc(obsc_, obsc_ + sizeof(obsc_) / sizeof(*obsc_)); > 176 string _ = "?"; > 177 END > 178 } > 179 // END CUT HERE
Added SRM/TCO20-3B-U/1B.cpp version [2ee42b04a811c9f2]
> 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 class ShortBugPaths { public: > 39 int count(int N, vector <int> D, int J) > 40 { > 41 if (N <= 200) { > 42 vector<vector<int>> c(N, vector<int>(N, 1)); > 43 vector<vector<int>> c2(N, vector<int>(N, 1)); > 44 for (int _ = 0; _ < J; ++_) { > 45 for (int y = 0; y < N; ++y) > 46 for (int x = 0; x < N; ++x) { > 47 LL sum = 0; > 48 for (int DD : D) { > 49 int yy = y - DD, xx = x; > 50 for (int d = 0; d < DD; ++d) { > 51 if (0 <= yy&&yy<N && 0 < > 52 yy++, xx++; > 53 } > 54 for (int d = 0; d < DD; ++d) { > 55 if (0 <= yy&&yy<N && 0 < > 56 yy++, xx--; > 57 } > 58 for (int d = 0; d < DD; ++d) { > 59 if (0 <= yy&&yy<N && 0 < > 60 yy--, xx--; > 61 } > 62 for (int d = 0; d < DD; ++d) { > 63 if (0 <= yy&&yy<N && 0 < > 64 yy--, xx++; > 65 } > 66 if (DD == 0) > 67 sum += c[y][x]; > 68 } > 69 c2[y][x] = sum % MODVAL; > 70 } > 71 c.swap(c2); > 72 } > 73 mint ans = 0; > 74 for (int y = 0; y < N; ++y) > 75 for (int x = 0; x < N; ++x) > 76 ans += c[y][x]; > 77 return ans.val; > 78 } > 79 else { > 80 vector<vector<int>> c(201, vector<int>(201, 1)); > 81 vector<vector<int>> c2(201, vector<int>(201, 1)); > 82 for (int _ = 0; _ < J; ++_) { > 83 for (int y = 0; y < 101; ++y) > 84 for (int x = 0; x < 101; ++x) { > 85 LL sum = 0; > 86 for (int DD : D) { > 87 int yy = y - DD, xx = x; > 88 > 89 if (y == 100 && x == 100 > 90 for (int d = 0; > 91 if (0 <= > 92 yy++, xx > 93 } > 94 for (int d = 0; > 95 if (0 <= > 96 yy++, xx > 97 } > 98 for (int d = 0; > 99 if (0 <= > 100 yy--, xx > 101 } > 102 for (int d = 0; > 103 if (0 <= > 104 yy--, xx > 105 } > 106 } > 107 else if (y == 100) { > 108 for (int d = 0; > 109 if (0 <= > 110 yy++, xx > 111 } > 112 for (int d = 0; > 113 if (0 <= > 114 yy++, xx > 115 } > 116 for (int d = 0; > 117 if (0 <= > 118 yy--, xx > 119 } > 120 for (int d = 0; > 121 if (0 <= > 122 yy--, xx > 123 } > 124 } > 125 else if (x == 100) { > 126 for (int d = 0; > 127 if (0 <= > 128 yy++, xx > 129 } > 130 for (int d = 0; > 131 if (0 <= > 132 yy++, xx > 133 } > 134 for (int d = 0; > 135 if (0 <= > 136 yy--, xx > 137 } > 138 for (int d = 0; > 139 if (0 <= > 140 yy--, xx > 141 } > 142 } > 143 else { > 144 for (int d = 0; > 145 if (0 <= > 146 yy++, xx > 147 } > 148 for (int d = 0; > 149 if (0 <= > 150 yy++, xx > 151 } > 152 for (int d = 0; > 153 if (0 <= > 154 yy--, xx > 155 } > 156 for (int d = 0; > 157 if (0 <= > 158 yy--, xx > 159 } > 160 } > 161 > 162 if (DD == 0) > 163 sum += c[y][x]; > 164 } > 165 c2[y][x] = sum % MODVAL; > 166 } > 167 for (int y = 0; y < 201; ++y) > 168 for (int x = 0; x < 201; ++x) > 169 c2[y][x] = c2[y>100 ? 200-y : y] > 170 c.swap(c2); > 171 } > 172 mint ans = 0; > 173 for (int y = 0; y < 201; ++y) > 174 for (int x = 0; x < 201; ++x) > 175 if (y == 100 && x == 100) > 176 ans += mint(c[y][x]) * (N - 200) > 177 else if (y == 100 || x == 100) > 178 ans += mint(c[y][x]) * (N - 200) > 179 else > 180 ans += c[y][x]; > 181 return ans.val; > 182 } > 183 } > 184 }; > 185 > 186 // BEGIN CUT HERE > 187 #include <ctime> > 188 double start_time; string timer() > 189 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 190 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 191 { os << "{ "; > 192 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 193 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 194 void verify_case(const int& Expected, const int& Received) { > 195 bool ok = (Expected == Received); > 196 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 197 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 198 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 199 #define END verify_case(_, ShortBugPaths().count(N, D, J));} > 200 int main(){ > 201 > 202 CASE(0) > 203 int N = 3; > 204 int D_[] = {1}; > 205 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 206 int J = 1; > 207 int _ = 24; > 208 END > 209 CASE(1) > 210 int N = 123456789; > 211 int D_[] = {0}; > 212 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 213 int J = 3; > 214 int _ = 643499475; > 215 END > 216 CASE(2) > 217 int N = 5; > 218 int D_[] = {0, 10, 2}; > 219 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 220 int J = 4; > 221 int _ = 38281; > 222 END > 223 CASE(3) > 224 int N = 1000; > 225 int D_[] = {0,1}; > 226 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 227 int J = 1; > 228 int _ = 4996000; > 229 END > 230 CASE(4) > 231 int N = 47; > 232 int D_[] = {3}; > 233 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 234 int J = 6; > 235 int _ = 195354165; > 236 END > 237 CASE(5) > 238 int N = 200; > 239 int D_[] = { 0,1,2,3,4,5,6,7,8,9,10 }; > 240 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 241 int J = 10; > 242 int _ = 316860289; > 243 END > 244 CASE(6) > 245 int N = 1000000000; > 246 int D_[] = { 0,1,2,3,4,5,6,7,8,9,10 }; > 247 vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); > 248 int J = 10; > 249 int _ = -100; > 250 END > 251 } > 252 // END CUT HERE