Overview
| SHA1 Hash: | 91eacbb0eb468dc7bae17a393a6cf1f615c8e9b0 |
|---|---|
| Date: | 2017-07-22 17:53:42 |
| User: | kinaba |
| Comment: | TCO17 R2C |
| 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/TCO17-2C-U/1A.cpp version [a42c7d53ea89e664]
> 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 CanidsSeesaw { public: > 23 vector <int> construct(vector <int> wolf, vector <int> fox, int k) > 24 { > 25 partial_sum(wolf.begin(), wolf.end(), wolf.begin()); > 26 > 27 vector<pair<int, int>> fox_idx; > 28 for (int i = 0; i < fox.size(); ++i) > 29 fox_idx.emplace_back(fox[i], i); > 30 > 31 sort(fox_idx.rbegin(), fox_idx.rend()); > 32 while (point_of(fox_idx, wolf) > k) { > 33 bool swapped = false; > 34 for(int i=0; i+1<fox_idx.size(); ++i) > 35 if (fox_idx[i] > fox_idx[i + 1]) > 36 { > 37 swap(fox_idx[i], fox_idx[i + 1]); > 38 swapped = true; > 39 break; > 40 } > 41 if (!swapped)break; > 42 } > 43 > 44 if (point_of(fox_idx, wolf) == k) { > 45 vector<int> idx; > 46 for (auto fi : fox_idx) > 47 idx.push_back(fi.second); > 48 return idx; > 49 } > 50 return vector<int>(); > 51 } > 52 > 53 int point_of(const vector<pair<int,int>>& fox_idx, const vector<int>& wo > 54 int score = 0, cur = 0; > 55 for (int i = 0; i < fox_idx.size(); ++i) { > 56 cur += fox_idx[i].first; > 57 if (cur > wolf_sum[i]) > 58 ++score; > 59 } > 60 return score; > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, CanidsSeesaw().construct(wolf, fox, k));} > 78 int main(){ > 79 > 80 CASE(0) > 81 int wolf_[] = {3,1}; > 82 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 83 int fox_[] = {4,2}; > 84 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 85 int k = 1; > 86 int __[] = {1, 0 }; > 87 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 88 END > 89 CASE(1) > 90 int wolf_[] = {1,3}; > 91 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 92 int fox_[] = {4,2}; > 93 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 94 int k = 1; > 95 vector <int> _; > 96 END > 97 CASE(2) > 98 int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; > 99 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 100 int fox_[] = {1,100,1,100,1,100,1,100,1,100}; > 101 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 102 int k = 7; > 103 int __[] = {0, 2, 4, 1, 6, 3, 5, 7, 9, 8 }; > 104 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(3) > 107 int wolf_[] = {10,10,10,10,10,10,10,10,10,10}; > 108 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 109 int fox_[] = {1,100,1,100,1,100,1,100,1,100}; > 110 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 111 int k = 4; > 112 vector <int> _; > 113 END > 114 CASE(4) > 115 int wolf_[] = {2}; > 116 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 117 int fox_[] = {1}; > 118 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 119 int k = 0; > 120 int __[] = {0 }; > 121 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 122 END > 123 /* > 124 CASE(5) > 125 int wolf_[] = ; > 126 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 127 int fox_[] = ; > 128 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 129 int k = ; > 130 int __[] = ; > 131 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 132 END > 133 CASE(6) > 134 int wolf_[] = ; > 135 vector <int> wolf(wolf_, wolf_+sizeof(wolf_)/sizeof(*wolf_)); > 136 int fox_[] = ; > 137 vector <int> fox(fox_, fox_+sizeof(fox_)/sizeof(*fox_)); > 138 int k = ; > 139 int __[] = ; > 140 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 141 END > 142 */ > 143 } > 144 // END CUT HERE
Added SRM/TCO17-2C-U/1B.cpp version [ce17f42a8e0e96e1]
> 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 template<typename Vert=int, typename Flow=int, int NV = 50> > 23 class MaxFlow > 24 { > 25 vector<int> G[NV]; > 26 Flow F[NV][NV]; > 27 > 28 public: > 29 void addEdge(Vert s, Vert t) > 30 { > 31 G[s].push_back(t); > 32 G[t].push_back(s); > 33 F[s][t] = 1; > 34 F[t][s] = 1; > 35 } > 36 > 37 Flow calc(Vert S, Vert D) > 38 { > 39 for (Flow total = 0;; ) { > 40 // Do BFS and compute the level for each node. > 41 int LV[NV] = { 0 }; > 42 vector<int> Q(1, S); > 43 for (int lv = 1; !Q.empty(); ++lv) { > 44 vector<int> Q2; > 45 for (size_t i = 0; i != Q.size(); ++i) { > 46 const vector<int>& ne = G[Q[i]]; > 47 for (size_t j = 0; j != ne.size(); ++j) > 48 if (F[Q[i]][ne[j]] && !LV[ne[j]] > 49 LV[ne[j]] = lv, Q2.push_ > 50 } > 51 Q.swap(Q2); > 52 } > 53 > 54 // Destination is now unreachable. Done. > 55 if (!LV[D]) > 56 return total; > 57 > 58 // Iterating DFS. > 59 bool blocked[NV] = {}; > 60 total += dinic_dfs(S, D, LV, 0x7fffffff, blocked); > 61 } > 62 } > 63 > 64 private: > 65 Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[]) > 66 { > 67 Flow flow_out = 0; > 68 for (size_t i = 0; i != G[v].size(); ++i) { > 69 int u = G[v][i]; > 70 if (LV[v] + 1 == LV[u] && F[v][u]) { > 71 Flow f = min(flow_in - flow_out, F[v][u]); > 72 if (u == D || !blocked[u] && (f = dinic_dfs(u, D > 73 F[v][u] -= f; > 74 F[u][v] += f; > 75 flow_out += f; > 76 if (flow_in == flow_out) return flow_out > 77 } > 78 } > 79 } > 80 blocked[v] = (flow_out == 0); > 81 return flow_out; > 82 } > 83 }; > 84 > 85 class AngelDemonGame { public: > 86 string winner(vector <string> G, int A, int D) > 87 { > 88 const int N = G.size(); > 89 if (D >= N - 1) > 90 return "Demon"; // by cutting all the edges around 0. > 91 > 92 // Since A>=2, there are at least (n-1) way > 93 // 0--(n-1) or 0--k--(n-1) for all k > 94 // possible and disjoint paths. Devil cannot prevent all of them > 95 // If and only if Angle can make mincut > D, Angle certainly win > 96 // Otherwise Demon may luckily choose the mincut. > 97 return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown > 98 } > 99 > 100 bool canMakeMinCutLargerThanD(int N, vector<string> G, int A, int D) > 101 { > 102 if (G[0][N - 1] == 'N') { > 103 G[0][N - 1] = G[N - 1][0] = 'Y'; > 104 --A; > 105 } > 106 > 107 set<int> Lchance, Rchance; > 108 for (int u = 1; u < N - 1; ++u) { > 109 if (G[0][u] == 'N') Lchance.insert(u); > 110 if (G[u][N-1] == 'N') Rchance.insert(u); > 111 } > 112 > 113 int cur = minCut(N, G); > 114 while(cur <= D && A > 0) { > 115 for (int u : Lchance) { > 116 G[0][u] = G[u][0] = 'Y'; > 117 if (minCut(N, G) > cur) { > 118 --A; > 119 ++cur; > 120 Lchance.erase(u); > 121 goto next; > 122 } > 123 G[0][u] = G[u][0] = 'N'; > 124 } > 125 for (int u : Rchance) { > 126 G[u][N-1] = G[N-1][u] = 'Y'; > 127 if (minCut(N, G) > cur) { > 128 --A; > 129 ++cur; > 130 Rchance.erase(u); > 131 goto next; > 132 } > 133 G[u][N - 1] = G[N - 1][u] = 'N'; > 134 } > 135 > 136 if (!Lchance.empty()) { > 137 int u = *Lchance.begin(); > 138 G[0][u] = G[u][0] = 'Y'; > 139 Lchance.erase(u); > 140 --A; > 141 goto next; > 142 } > 143 if (!Rchance.empty()) { > 144 int u = *Rchance.begin(); > 145 G[0][u] = G[u][0] = 'Y'; > 146 Rchance.erase(u); > 147 --A; > 148 goto next; > 149 } > 150 next:; > 151 } > 152 > 153 return cur > D; > 154 } > 155 > 156 int minCut(int N, const vector<string>& G) > 157 { > 158 MaxFlow<> mf; > 159 for (int u = 0; u < N; ++u) > 160 for (int v = u + 1; v < N; ++v) > 161 if (G[u][v] == 'Y') > 162 mf.addEdge(u, v); > 163 return mf.calc(0, N - 1); > 164 } > 165 }; > 166 > 167 // BEGIN CUT HERE > 168 #include <ctime> > 169 double start_time; string timer() > 170 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 171 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 172 { os << "{ "; > 173 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 174 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 175 void verify_case(const string& Expected, const string& Received) { > 176 bool ok = (Expected == Received); > 177 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 178 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 179 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 180 #define END verify_case(_, AngelDemonGame().winner(G, A, D));} > 181 int main(){ > 182 > 183 CASE(0) > 184 string G_[] = {"NYNY", > 185 "YNYY", > 186 "NYNN", > 187 "YYNN"}; > 188 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 189 int A = 2; > 190 int D = 2; > 191 string _ = "Angel"; > 192 END > 193 CASE(1) > 194 string G_[] = {"NYNY", > 195 "YNYY", > 196 "NYNN", > 197 "YYNN"}; > 198 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 199 int A = 6; > 200 int D = 6; > 201 string _ = "Demon"; > 202 END > 203 CASE(2) > 204 string G_[] = {"NNNN", > 205 "NNNN", > 206 "NNNN", > 207 "NNNN"}; > 208 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 209 int A = 2; > 210 int D = 2; > 211 string _ = "Unknown"; > 212 END > 213 CASE(3) > 214 string G_[] = {"NYNNNY", > 215 "YNNYNN", > 216 "NNNNYN", > 217 "NYNNNN", > 218 "NNYNNN", > 219 "YNNNNN"}; > 220 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 221 int A = 4; > 222 int D = 4; > 223 string _ = "Unknown"; > 224 END > 225 CASE(4) > 226 string G_[] = {"NYNNNY", > 227 "YNNYNN", > 228 "NNNNYN", > 229 "NYNNNN", > 230 "NNYNNN", > 231 "YNNNNN"}; > 232 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 233 int A = 8; > 234 int D = 4; > 235 string _ = "Angel"; > 236 END > 237 CASE(5) > 238 string G_[] = {"NYNNNY", > 239 "YNNYNN", > 240 "NNNNYN", > 241 "NYNNNN", > 242 "NNYNNN", > 243 "YNNNNN"}; > 244 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 245 int A = 4; > 246 int D = 8; > 247 string _ = "Demon"; > 248 END > 249 CASE(6) > 250 string G_[] = { "NNNN","NNNN","NNNN","NNNN" }; > 251 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 252 int A = 4; > 253 int D = 2; > 254 string _ = "Unknown"; > 255 END > 256 /* > 257 CASE(7) > 258 string G_[] = ; > 259 vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_)); > 260 int A = ; > 261 int D = ; > 262 string _ = ; > 263 END > 264 */ > 265 } > 266 // END CUT HERE