976.md (8090B)
1 Source: https://codeforces.com/blog/entry/59195 2 3 [976A - Minimum Binary Number](/contest/976/problem/A "Educational Codeforces Round 43 (Rated for Div. 2)") 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int n; 23 string s; 24 cin >> n >> s; 25 if (n == 1) { 26 cout << s << endl; 27 } else { 28 int cnt0 = 0; 29 for (int i = 0; i < n; ++i) 30 cnt0 += s[i] == '0'; 31 cout << 1; 32 for (int i = 0; i < cnt0; ++i) 33 cout << 0; 34 cout << endl; 35 } 36 37 return 0; 38 } 39 ``` 40 41 [976B - Lara Croft and the New Game](/contest/976/problem/B "Educational Codeforces Round 43 (Rated for Div. 2)") 42 43 **Editorial** 44 45 Tutorial is loading... 46 47 **Solution (PikMike)** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 #define forn(i, n) for (int i = 0; i < int(n); i++) 53 54 using namespace std; 55 56 int n, m; 57 long long k; 58 59 int main() { 60 scanf("%d%d%lld", &n, &m, &k); 61 if (k < n){ 62 printf("%lld 1\n", k + 1); 63 return 0; 64 } 65 k -= n; 66 long long row = k / (m - 1); 67 printf("%lld ", n - row); 68 if (row & 1) 69 printf("%lld\n", m - k % (m - 1)); 70 else 71 printf("%lld\n", k % (m - 1) + 2); 72 return 0; 73 } 74 ``` 75 76 [976C - Nested Segments](/contest/976/problem/C "Educational Codeforces Round 43 (Rated for Div. 2)") 77 78 **Editorial** 79 80 Tutorial is loading... 81 82 **Solution (PikMike)** 83 84 ``` 85 #include <bits/stdc++.h> 86 87 #define forn(i, n) for (int i = 0; i < int(n); i++) 88 #define x first 89 #define y second 90 91 using namespace std; 92 93 typedef pair<int, int> pt; 94 95 const int N = 300 * 1000 + 13; 96 97 int n; 98 pair<pt, int> a[N]; 99 100 int main() { 101 scanf("%d", &n); 102 forn(i, n){ 103 scanf("%d%d", &a[i].x.x, &a[i].x.y); 104 a[i].y = i + 1; 105 } 106 107 sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;}); 108 109 set<pt> cur; 110 forn(i, n){ 111 while (!cur.empty() && cur.begin()->x < a[i].x.x) 112 cur.erase(cur.begin()); 113 if (!cur.empty() && (--cur.end())->x >= a[i].x.y){ 114 printf("%d %d\n", a[i].y, (--cur.end())->y); 115 return 0; 116 } 117 cur.insert({a[i].x.y, a[i].y}); 118 } 119 120 puts("-1 -1"); 121 return 0; 122 } 123 ``` 124 125 [976D - Degree Set](/contest/976/problem/D "Educational Codeforces Round 43 (Rated for Div. 2)") 126 127 **Editorial** 128 129 Tutorial is loading... 130 131 **Solution (PikMike)** 132 133 ``` 134 #include <bits/stdc++.h> 135 136 #define forn(i, n) for (int i = 0; i < int(n); i++) 137 138 using namespace std; 139 140 typedef pair<int, int> pt; 141 142 const int N = 100 * 1000 + 13; 143 144 int n; 145 vector<int> d; 146 vector<int> g[N]; 147 148 vector<pt> construct(int st, vector<int> d){ 149 if (d.empty()) 150 return vector<pt>(); 151 152 vector<pt> res; 153 forn(i, d[0]) 154 for (int j = st + i + 1; j <= st + d.back(); ++j) 155 res.push_back({st + i, j}); 156 157 int nxt = st + d[0]; 158 for (int i = 1; i < int(d.size()); ++i) 159 d[i] -= d[0]; 160 d.erase(d.begin()); 161 if (!d.empty()) 162 d.pop_back(); 163 164 auto tmp = construct(nxt, d); 165 for (auto it : tmp) 166 res.push_back(it); 167 168 return res; 169 } 170 171 int main() { 172 scanf("%d", &n); 173 d.resize(n); 174 forn(i, n) 175 scanf("%d", &d[i]); 176 auto res = construct(0, d); 177 printf("%d\n", int(res.size())); 178 for (auto it : res) 179 printf("%d %d\n", it.first + 1, it.second + 1); 180 return 0; 181 } 182 ``` 183 184 [976E - Well played!](/contest/976/problem/E "Educational Codeforces Round 43 (Rated for Div. 2)") 185 186 **Editorial** 187 188 Tutorial is loading... 189 190 **Solution (Ajosteen)** 191 192 ``` 193 #include <bits/stdc++.h> 194 195 using namespace std; 196 197 const int N = 200 * 1000 + 9; 198 199 int n, a, b; 200 int hp[N], dmg[N]; 201 202 bool cmp(int i, int j){ 203 if(hp[i] - dmg[i] != hp[j] - dmg[j]) 204 return hp[i] - dmg[i] > hp[j] - dmg[j]; 205 return i < j; 206 } 207 208 int get(int id){ 209 return hp[id] > dmg[id]? hp[id] : dmg[id]; 210 } 211 212 int main(){ 213 scanf("%d %d %d", &n, &a, &b); 214 for(int i = 0; i < n; ++i) 215 scanf("%d %d", hp + i, dmg + i); 216 217 b = min(b, n); 218 vector <int> p(n); 219 for(int i = 0; i < n; ++i) p[i] = i; 220 sort(p.begin(), p.end(), cmp); 221 long long res = 0, sum = 0; 222 for(int i = 0; i < n; ++i){ 223 int id = p[i]; 224 if(i < b) sum += get(id); 225 else sum += dmg[id]; 226 } 227 res = sum; 228 229 if(b == 0){ 230 printf("%lld\n", res); 231 return 0; 232 } 233 234 long long x = (1LL << a); 235 for(int i = 0; i < n; ++i){ 236 int id = p[i]; 237 long long nres = sum; 238 if(i < b){ 239 nres -= get(id); 240 nres += hp[id] * x; 241 res = max(res, nres); 242 } 243 else{ 244 nres -= dmg[id]; 245 nres += hp[id] * x; 246 int id2 = p[b - 1]; 247 nres -= get(id2); 248 nres += dmg[id2]; 249 res = max(res, nres); 250 251 } 252 } 253 254 printf("%lld\n", res); 255 return 0; 256 } 257 ``` 258 259 [976F - Minimal k-covering](/contest/976/problem/F "Educational Codeforces Round 43 (Rated for Div. 2)") 260 261 **Editorial** 262 263 Tutorial is loading... 264 265 **Solution (adedalic)** 266 267 ``` 268 #include<bits/stdc++.h> 269 270 using namespace std; 271 272 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 273 274 #define sz(a) int((a).size()) 275 #define x first 276 #define y second 277 278 const int INF = int(1e9); 279 const int N = 4221; 280 281 struct edge { 282 int to, c, f, id; 283 284 edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {} 285 }; 286 287 vector<edge> es; 288 vector<int> g[N]; 289 290 void add_edge(int fr, int to, int cap, int id) { 291 g[fr].push_back(sz(es)); 292 es.emplace_back(to, cap, 0, id); 293 g[to].push_back(sz(es)); 294 es.emplace_back(fr, 0, 0, id); 295 } 296 297 int pw[N]; 298 int n1, n2, m; 299 300 inline bool read() { 301 if(!(cin >> n1 >> n2 >> m)) 302 return false; 303 304 fore(id, 0, m) { 305 int u, v; 306 assert(cin >> u >> v); 307 u--, v--; 308 309 pw[u]++; 310 pw[n1 + v]++; 311 312 add_edge(u, n1 + v, 1, id); 313 } 314 return true; 315 } 316 317 int d[N], q[N], hd, tl; 318 inline bool bfs(int s, int t, int n) { 319 fore(i, 0, n) 320 d[i] = INF; 321 hd = tl = 0; 322 323 d[s] = 0; 324 q[tl++] = s; 325 while(hd != tl) { 326 int v = q[hd++]; 327 if(v == t) 328 break; 329 330 for(int id : g[v]) { 331 if(es[id].c - es[id].f == 0) 332 continue; 333 334 int to = es[id].to; 335 if(d[to] > d[v] + 1) { 336 d[to] = d[v] + 1; 337 q[tl++] = to; 338 } 339 } 340 } 341 return d[t] < INF; 342 } 343 344 int nxt[N]; 345 346 int dfs(int v, int t, int mx) { 347 if(v == t) return mx; 348 if(mx == 0) return 0; 349 350 int sum = 0; 351 for(; nxt[v] < sz(g[v]); nxt[v]++) { 352 int id = g[v][nxt[v]]; 353 int rem = es[id].c - es[id].f; 354 int to = es[id].to; 355 356 if(rem == 0 || d[to] != d[v] + 1) 357 continue; 358 359 int cur = 0; 360 if((cur = dfs(to, t, min(mx - sum, rem))) > 0) { 361 es[id].f += cur; 362 es[id ^ 1].f -= cur; 363 sum += cur; 364 } 365 366 if(sum == mx) 367 break; 368 } 369 return sum; 370 } 371 372 inline int dinic(int s, int t, int n) { 373 int mf = 0; 374 while(bfs(s, t, n)) { 375 fore(i, 0, n) 376 nxt[i] = 0; 377 378 int cf = 0; 379 while((cf = dfs(s, t, INF)) > 0) 380 mf += cf; 381 } 382 return mf; 383 } 384 385 vector<int> res[N]; 386 387 inline void getCert(int k) { 388 fore(v, 0, n1) { 389 for(int id : g[v]) { 390 if(es[id].to < n1 || es[id].to >= n1 + n2) 391 continue; 392 assert(es[id].c > 0); 393 if(es[id].f > 0) 394 continue; 395 396 res[k].push_back(es[id].id); 397 } 398 } 399 } 400 401 void solve() { 402 int cnt = *min_element(pw, pw + n1 + n2); 403 404 int s = n1 + n2; int t = s + 1; 405 fore(i, 0, n1) 406 add_edge(s, i, pw[i] - cnt, -1); 407 fore(i, n1, n1 + n2) 408 add_edge(i, t, pw[i] - cnt, -1); 409 410 int mf = 0, mn = cnt; 411 while(mn >= 0) { 412 mf += dinic(s, t, n1 + n2 + 2); 413 getCert(mn); 414 415 if(mn > 0) { 416 for (int id : g[s]) { 417 assert(es[id].id < 0); 418 assert((id & 1) == 0); 419 es[id].c++; 420 } 421 for (int id : g[t]) { 422 assert(es[id].id < 0); 423 assert(es[id].c == 0); 424 es[id ^ 1].c++; 425 } 426 } 427 mn--; 428 } 429 430 fore(i, 0, cnt + 1) { 431 printf("%d ", sz(res[i])); 432 for(int id : res[i]) 433 printf("%d ", id + 1); 434 puts(""); 435 } 436 } 437 438 int main() { 439 #ifdef _DEBUG 440 freopen("input.txt", "r", stdin); 441 #endif 442 443 if(read()) { 444 solve(); 445 } 446 return 0; 447 } 448 ```