1288.md (11589B)
1 Source: https://codeforces.com/blog/entry/73105 2 3 [1288A - Deadline](/contest/1288/problem/A "Educational Codeforces Round 80 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // int tt = clock(); 22 #endif 23 24 int T; cin >> T; 25 while(T--) { 26 int n, d; 27 cin >> n >> d; 28 29 int x, MAG = (int)sqrt(d) + 10; 30 for(x = 0; x < MAG; x++) { 31 if(x + (d + x) / (x + 1) <= n) 32 break; 33 } 34 cout << (x < MAG ? "YES" : "NO") << endl; 35 } 36 37 return 0; 38 } 39 ``` 40 41 [1288B - Yet Another Meme Problem](/contest/1288/problem/B "Educational Codeforces Round 80 (Rated for Div. 2)") 42 43 Idea: [Roms](/profile/Roms "Master Roms") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution (Roms)** 50 51 ``` 52 for t in range(int(input())): 53 a, b = map(int, input().split()) 54 print(a * (len(str(b + 1)) - 1)) 55 ``` 56 57 [1288C - Two Arrays](/contest/1288/problem/C "Educational Codeforces Round 80 (Rated for Div. 2)") 58 59 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 60 61 **Tutorial** 62 63 Tutorial is loading... 64 65 **Solution (Roms)** 66 67 ``` 68 from math import factorial as fact 69 mod = 10**9 + 7 70 71 def C(n, k): 72 return fact(n) // (fact(k) * fact(n - k)) 73 74 n, m = map(int, input().split()) 75 print(C(n + 2*m - 1, 2*m) % mod) 76 ``` 77 78 [1288D - Minimax Problem](/contest/1288/problem/D "Educational Codeforces Round 80 (Rated for Div. 2)") 79 80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution (BledDest)** 87 88 ``` 89 #include<bits/stdc++.h> 90 91 using namespace std; 92 93 int n, m; 94 vector<vector<int> > a; 95 int a1, a2; 96 97 bool can(int mid) 98 { 99 vector<int> msk(1 << m, -1); 100 for(int i = 0; i < n; i++) 101 { 102 int cur = 0; 103 for(int j = 0; j < m; j++) 104 if(a[i][j] >= mid) 105 cur ^= (1 << j); 106 msk[cur] = i; 107 } 108 if(msk[(1 << m) - 1] != -1) 109 { 110 a1 = a2 = msk[(1 << m) - 1]; 111 return true; 112 } 113 for(int i = 0; i < (1 << m); i++) 114 for(int j = 0; j < (1 << m); j++) 115 if(msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1) 116 { 117 a1 = msk[i]; 118 a2 = msk[j]; 119 return true; 120 } 121 return false; 122 } 123 124 int main() 125 { 126 scanf("%d %d", &n, &m); 127 a.resize(n, vector<int>(m)); 128 for(int i = 0; i < n; i++) 129 for(int j = 0; j < m; j++) 130 scanf("%d", &a[i][j]); 131 int lf = 0; 132 int rg = int(1e9) + 43; 133 while(rg - lf > 1) 134 { 135 int m = (lf + rg) / 2; 136 if(can(m)) 137 lf = m; 138 else 139 rg = m; 140 } 141 assert(can(lf)); 142 printf("%d %d\n", a1 + 1, a2 + 1); 143 } 144 ``` 145 146 [1288E - Messenger Simulator](/contest/1288/problem/E "Educational Codeforces Round 80 (Rated for Div. 2)") 147 148 Idea: [Neon](/profile/Neon "Candidate Master Neon") 149 150 **Tutorial** 151 152 Tutorial is loading... 153 154 **Solution 1 (pikmike)** 155 156 ``` 157 #include <bits/stdc++.h> 158 159 #define forn(i, n) for (int i = 0; i < int(n); i++) 160 #define x first 161 #define y second 162 163 using namespace std; 164 165 const int N = 300 * 1000 + 13; 166 const int P = 550; 167 168 typedef pair<int, int> pt; 169 170 int n; 171 int a[N]; 172 vector<int> pos[N]; 173 pt ans[N]; 174 175 int cnt[N]; 176 int tot; 177 178 void add(int x){ 179 ++cnt[x]; 180 if (cnt[x] == 1) ++tot; 181 } 182 183 void rem(int x){ 184 if (cnt[x] == 1) --tot; 185 --cnt[x]; 186 } 187 188 int f[N]; 189 190 void upd(int x){ 191 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 192 ++f[i]; 193 } 194 195 int get(int x){ 196 int res = 0; 197 for (int i = x; i < N; i |= i + 1) 198 res += f[i]; 199 return res; 200 } 201 202 int main() { 203 int n, m; 204 scanf("%d%d", &n, &m); 205 forn(i, m){ 206 scanf("%d", &a[i]); 207 --a[i]; 208 } 209 forn(i, m){ 210 pos[a[i]].push_back(i); 211 } 212 213 vector<pt> qr; 214 forn(i, n){ 215 for (int j = 1; j < int(pos[i].size()); ++j) 216 qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1)); 217 if (!pos[i].empty()) 218 qr.push_back(make_pair(pos[i].back() + 1, m - 1)); 219 } 220 221 sort(qr.begin(), qr.end(), [](const pt &a, const pt &b){ 222 if (a.x / P != b.x / P) 223 return a.x < b.x; 224 if ((a.x / P) & 1) 225 return a.y < b.y; 226 return a.y > b.y; 227 }); 228 229 forn(i, n) ans[i] = {i, i}; 230 forn(i, m) ans[a[i]].x = 0; 231 232 int L = 0, R = -1; 233 forn(i, qr.size()){ 234 int l = qr[i].x; 235 int r = qr[i].y; 236 if (r < l) continue; 237 238 int x = a[qr[i].x - 1]; 239 while (L < l) rem(a[L++]); 240 while (L > l) add(a[--L]); 241 while (R > r) rem(a[R--]); 242 while (R < r) add(a[++R]); 243 244 ans[x].y = max(ans[x].y, tot); 245 } 246 forn(i, m){ 247 if (i == pos[a[i]][0]){ 248 ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i])); 249 upd(a[i]); 250 } 251 } 252 forn(i, n) if (pos[i].empty()){ 253 ans[i].y = max(ans[i].y, i + get(i)); 254 } 255 256 forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1); 257 return 0; 258 } 259 ``` 260 261 **Solution 2 (pikmike)** 262 263 ``` 264 #include <bits/stdc++.h> 265 266 #define forn(i, n) for (int i = 0; i < int(n); i++) 267 #define x first 268 #define y second 269 270 using namespace std; 271 272 const int N = 300 * 1000 + 13; 273 274 typedef pair<int, int> pt; 275 276 int n; 277 int a[N]; 278 vector<int> pos[N]; 279 pt ans[N]; 280 int prv[N]; 281 282 vector<int> t[4 * N]; 283 284 void build(int v, int l, int r){ 285 if (l == r - 1){ 286 t[v].push_back(prv[l]); 287 return; 288 } 289 int m = (l + r) / 2; 290 build(v * 2, l, m); 291 build(v * 2 + 1, m, r); 292 t[v].resize(r - l); 293 merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin()); 294 } 295 296 int get(int v, int l, int r, int L, int R, int val){ 297 if (L >= R) 298 return 0; 299 if (l == L && r == R) 300 return lower_bound(t[v].begin(), t[v].end(), val) - t[v].begin(); 301 int m = (l + r) / 2; 302 return get(v * 2, l, m, L, min(m, R), val) + get(v * 2 + 1, m, r, max(m, L), R, val); 303 } 304 305 int f[N]; 306 307 void upd(int x){ 308 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 309 ++f[i]; 310 } 311 312 int get(int x){ 313 int res = 0; 314 for (int i = x; i < N; i |= i + 1) 315 res += f[i]; 316 return res; 317 } 318 319 int main() { 320 int n, m; 321 scanf("%d%d", &n, &m); 322 forn(i, m){ 323 scanf("%d", &a[i]); 324 --a[i]; 325 } 326 forn(i, m){ 327 pos[a[i]].push_back(i); 328 } 329 330 vector<pt> qr; 331 forn(i, n){ 332 for (int j = 1; j < int(pos[i].size()); ++j) 333 qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1)); 334 if (!pos[i].empty()) 335 qr.push_back(make_pair(pos[i].back() + 1, m - 1)); 336 } 337 338 forn(i, n) ans[i] = {i, i}; 339 forn(i, m) ans[a[i]].x = 0; 340 341 forn(i, n){ 342 int cur = -1; 343 for (auto it : pos[i]){ 344 prv[it] = cur; 345 cur = it; 346 } 347 } 348 build(1, 0, m); 349 350 forn(i, qr.size()){ 351 int l = qr[i].x; 352 int r = qr[i].y; 353 if (r < l) continue; 354 int x = a[qr[i].x - 1]; 355 int cnt = get(1, 0, m, l, r + 1, l); 356 ans[x].y = max(ans[x].y, cnt); 357 } 358 359 forn(i, m){ 360 if (i == pos[a[i]][0]){ 361 ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i])); 362 upd(a[i]); 363 } 364 } 365 forn(i, n) if (pos[i].empty()){ 366 ans[i].y = max(ans[i].y, i + get(i)); 367 } 368 369 forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1); 370 return 0; 371 } 372 ``` 373 374 **Solution 3 (pikmike)** 375 376 ``` 377 #include <bits/stdc++.h> 378 379 #define forn(i, n) for (int i = 0; i < int(n); i++) 380 381 using namespace std; 382 383 const int N = 600 * 1000 + 13; 384 385 int f[N]; 386 387 void upd(int x, int val){ 388 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 389 f[i] += val; 390 } 391 392 int get(int x){ 393 int res = 0; 394 for (int i = x; i < N; i |= i + 1) 395 res += f[i]; 396 return res; 397 } 398 399 int main() { 400 int n, m; 401 scanf("%d%d", &n, &m); 402 vector<int> mn(n); 403 iota(mn.begin(), mn.end(), 0); 404 vector<int> mx = mn; 405 406 vector<int> a(m); 407 forn(i, m){ 408 scanf("%d", &a[i]); 409 --a[i]; 410 mn[a[i]] = 0; 411 } 412 413 vector<int> pos(n); 414 forn(i, n) pos[i] = n - i - 1; 415 forn(i, n) upd(i, 1); 416 417 forn(i, m){ 418 mx[a[i]] = max(mx[a[i]], get(pos[a[i]] + 1)); 419 upd(pos[a[i]], -1); 420 pos[a[i]] = i + n; 421 upd(pos[a[i]], 1); 422 } 423 forn(i, n){ 424 mx[i] = max(mx[i], get(pos[i] + 1)); 425 } 426 427 forn(i, n) printf("%d %d\n", mn[i] + 1, mx[i] + 1); 428 return 0; 429 } 430 ``` 431 432 [1288F - Red-Blue Graph](/contest/1288/problem/F "Educational Codeforces Round 80 (Rated for Div. 2)") 433 434 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 435 436 **Tutorial** 437 438 Tutorial is loading... 439 440 **Solution (BledDest)** 441 442 ``` 443 #include<bits/stdc++.h> 444 445 using namespace std; 446 447 const int N = 443; 448 449 int n1, n2, m, r, b; 450 string s1, s2; 451 int u[N]; 452 int v[N]; 453 454 struct edge 455 { 456 int y, c, f, cost; 457 edge() {}; 458 edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {}; 459 }; 460 461 int bal[N][N]; 462 int s, t, oldS, oldT, V; 463 vector<int> g[N]; 464 vector<edge> e; 465 466 void add(int x, int y, int c, int cost) 467 { 468 g[x].push_back(e.size()); 469 e.push_back(edge(y, c, 0, cost)); 470 g[y].push_back(e.size()); 471 e.push_back(edge(x, 0, 0, -cost)); 472 } 473 474 int rem(int num) 475 { 476 return e[num].c - e[num].f; 477 } 478 479 void add_LR(int x, int y, int l, int r, int cost) 480 { 481 int c = r - l; 482 if(l > 0) 483 { 484 add(s, y, l, cost); 485 add(x, t, l, cost); 486 } 487 if(c > 0) 488 { 489 add(x, y, c, cost); 490 } 491 } 492 493 int p[N]; 494 int d[N]; 495 int pe[N]; 496 int inq[N]; 497 498 bool enlarge() 499 { 500 for(int i = 0; i < V; i++) 501 { 502 d[i] = int(1e9); 503 p[i] = -1; 504 pe[i] = -1; 505 inq[i] = 0; 506 } 507 d[s] = 0; 508 queue<int> q; 509 q.push(s); 510 inq[s] = 1; 511 while(!q.empty()) 512 { 513 int k = q.front(); 514 q.pop(); 515 inq[k] = 0; 516 for(auto z : g[k]) 517 { 518 if(!rem(z)) continue; 519 if(d[e[z].y] > d[k] + e[z].cost) 520 { 521 p[e[z].y] = k; 522 pe[e[z].y] = z; 523 d[e[z].y] = d[k] + e[z].cost; 524 if(!inq[e[z].y]) 525 { 526 q.push(e[z].y); 527 inq[e[z].y] = 1; 528 } 529 } 530 } 531 } 532 if(p[t] == -1) 533 return false; 534 int cur = t; 535 while(cur != s) 536 { 537 e[pe[cur]].f++; 538 e[pe[cur] ^ 1].f--; 539 cur = p[cur]; 540 } 541 return true; 542 } 543 544 void add_edge(int x, int y) 545 { 546 add(x, y + n1, 1, r); 547 add(y + n1, x, 1, b); 548 } 549 550 void impose_left(int x) 551 { 552 if(s1[x] == 'R') 553 { 554 add_LR(oldS, x, 1, m, 0); 555 } 556 else if(s1[x] == 'B') 557 { 558 add_LR(x, oldT, 1, m, 0); 559 } 560 else 561 { 562 add(oldS, x, m, 0); 563 add(x, oldT, m, 0); 564 } 565 } 566 567 void impose_right(int x) 568 { 569 if(s2[x] == 'R') 570 { 571 add_LR(x + n1, oldT, 1, m, 0); 572 } 573 else if(s2[x] == 'B') 574 { 575 add_LR(oldS, x + n1, 1, m, 0); 576 } 577 else 578 { 579 add(oldS, x + n1, m, 0); 580 add(x + n1, oldT, m, 0); 581 } 582 } 583 584 void construct_bal() 585 { 586 for(int i = 0; i < n1; i++) 587 { 588 for(auto z : g[i]) 589 { 590 if(e[z].y >= n1 && e[z].y < n1 + n2) 591 bal[i][e[z].y - n1] += e[z].f; 592 } 593 } 594 } 595 596 void find_ans() 597 { 598 int res = 0; 599 string w = ""; 600 for(auto x : g[s]) 601 if(rem(x)) 602 { 603 cout << -1 << endl; 604 return; 605 } 606 for(int i = 0; i < m; i++) 607 { 608 if(bal[u[i]][v[i]] > 0) 609 { 610 bal[u[i]][v[i]]--; 611 res += r; 612 w += "R"; 613 } 614 else if(bal[u[i]][v[i]] < 0) 615 { 616 bal[u[i]][v[i]]++; 617 res += b; 618 w += "B"; 619 } 620 else w += "U"; 621 } 622 cout << res << endl << w << endl; 623 } 624 625 int main() 626 { 627 cin >> n1 >> n2 >> m >> r >> b; 628 cin >> s1; 629 cin >> s2; 630 for(int i = 0; i < m; i++) 631 { 632 cin >> u[i] >> v[i]; 633 u[i]--; 634 v[i]--; 635 } 636 637 oldS = n1 + n2; 638 oldT = oldS + 1; 639 s = oldT + 1; 640 t = s + 1; 641 V = t + 1; 642 643 for(int i = 0; i < n1; i++) 644 impose_left(i); 645 for(int i = 0; i < n2; i++) 646 impose_right(i); 647 for(int i = 0; i < m; i++) 648 add_edge(u[i], v[i]); 649 add(oldT, oldS, 100000, 0); 650 while(enlarge()); 651 construct_bal(); 652 find_ans(); 653 } 654 ```