1167.md (8734B)
1 Source: https://codeforces.com/blog/entry/67058 2 3 [1167A - Telephone Number](/contest/1167/problem/A "Educational Codeforces Round 65 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int n; 19 string s; 20 21 int main(){ 22 int tc; 23 cin >> tc; 24 for(int t = 0; t < tc; ++t){ 25 cin >> n >> s; 26 int pos = n; 27 for(int i = 0; i < n; ++i) 28 if(s[i] == '8'){ 29 pos = i; 30 break; 31 } 32 33 if(n - pos >= 11) 34 cout << "YES\n"; 35 else 36 cout << "NO\n"; 37 } 38 return 0; 39 } 40 ``` 41 42 [1167B - Lost Numbers](/contest/1167/problem/B "Educational Codeforces Round 65 (Rated for Div. 2)") 43 44 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution (BledDest)** 51 52 ``` 53 #include<bits/stdc++.h> 54 55 using namespace std; 56 57 vector<int> p = {4, 8, 15, 16, 23, 42}; 58 int ans[4]; 59 60 int main() 61 { 62 for(int i = 0; i < 4; i++) 63 { 64 cout << "? " << i + 1 << " " << i + 2 << endl; 65 cout.flush(); 66 cin >> ans[i]; 67 } 68 do 69 { 70 bool good = true; 71 for(int i = 0; i < 4; i++) 72 good &= (p[i] * p[i + 1] == ans[i]); 73 if(good) break; 74 } 75 while(next_permutation(p.begin(), p.end())); 76 cout << "!"; 77 for(int i = 0; i < 6; i++) 78 cout << " " << p[i]; 79 cout << endl; 80 cout.flush(); 81 return 0; 82 } 83 ``` 84 85 [1167C - News Distribution](/contest/1167/problem/C "Educational Codeforces Round 65 (Rated for Div. 2)") 86 87 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution (BledDest)** 94 95 ``` 96 #include<bits/stdc++.h> 97 using namespace std; 98 99 const int N = 1000043; 100 vector<int> g[N]; 101 102 int color[N]; 103 int siz[N]; 104 int n, m; 105 int cc = 0; 106 107 int dfs(int x) 108 { 109 if(color[x]) 110 return 0; 111 color[x] = cc; 112 int ans = (x < n ? 1 : 0); 113 for(auto y : g[x]) 114 ans += dfs(y); 115 return ans; 116 } 117 118 int main() 119 { 120 scanf("%d %d", &n, &m); 121 for(int i = 0; i < m; i++) 122 { 123 int k; 124 scanf("%d", &k); 125 for(int j = 0; j < k; j++) 126 { 127 int x; 128 scanf("%d", &x); 129 --x; 130 g[x].push_back(i + n); 131 g[i + n].push_back(x); 132 } 133 } 134 for(int i = 0; i < n; i++) 135 { 136 if(!color[i]) 137 { 138 cc++; 139 siz[cc] = dfs(i); 140 } 141 printf("%d ", siz[color[i]]); 142 } 143 } 144 ``` 145 146 **Solution (PikMike)** 147 148 ``` 149 #include <bits/stdc++.h> 150 151 using namespace std; 152 153 #define forn(i, n) for(int i = 0; i < int(n); i++) 154 155 const int N = 500 * 1000 + 13; 156 157 int n, m; 158 int rk[N], p[N]; 159 160 int getP(int a){ 161 return (a == p[a] ? a : p[a] = getP(p[a])); 162 } 163 164 void unite(int a, int b){ 165 a = getP(a), b = getP(b); 166 if (a == b) return; 167 if (rk[a] < rk[b]) swap(a, b); 168 p[b] = a; 169 rk[a] += rk[b]; 170 } 171 172 int main(){ 173 scanf("%d%d", &n, &m); 174 forn(i, n) p[i] = i, rk[i] = 1; 175 176 forn(i, m){ 177 int k; 178 scanf("%d", &k); 179 int lst = -1; 180 forn(j, k){ 181 int x; 182 scanf("%d", &x); 183 --x; 184 if (lst != -1) 185 unite(x, lst); 186 lst = x; 187 } 188 } 189 190 forn(i, n) 191 printf("%d ", rk[getP(i)]); 192 puts(""); 193 } 194 ``` 195 196 [1167D - Bicolored RBS](/contest/1167/problem/D "Educational Codeforces Round 65 (Rated for Div. 2)") 197 198 Idea: [adedalic](/profile/adedalic "International Master adedalic") 199 200 **Tutorial** 201 202 Tutorial is loading... 203 204 **Solution (adedalic)** 205 206 ``` 207 #include<bits/stdc++.h> 208 using namespace std; 209 210 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 211 #define sz(a) int((a).size()) 212 213 int n; 214 string s; 215 216 inline bool read() { 217 if(!(cin >> n)) 218 return false; 219 cin >> s; 220 return true; 221 } 222 223 inline void solve() { 224 string t(n, '0'); 225 226 int bal = 0; 227 fore(i, 0, n) { 228 if(s[i] == ')') 229 bal--; 230 231 t[i] = char('0' + (bal & 1)); 232 233 if(s[i] == '(') 234 bal++; 235 } 236 237 cout << t << endl; 238 } 239 240 int main() { 241 #ifdef _DEBUG 242 freopen("input.txt", "r", stdin); 243 int tt = clock(); 244 #endif 245 246 if(read()) { 247 solve(); 248 249 #ifdef _DEBUG 250 cerr << "TIME = " << clock() - tt << endl; 251 tt = clock(); 252 #endif 253 } 254 return 0; 255 } 256 ``` 257 258 [1167E - Range Deleting](/contest/1167/problem/E "Educational Codeforces Round 65 (Rated for Div. 2)") 259 260 Idea: [Roms](/profile/Roms "Master Roms") 261 262 **Tutorial** 263 264 Tutorial is loading... 265 266 **Solution (Roms)** 267 268 ``` 269 #include <bits/stdc++.h> 270 271 using namespace std; 272 273 const int N = int(1e6) + 99; 274 int n, x; 275 int a[N]; 276 vector <int> pos[N]; 277 int prefMax[N]; 278 279 int main() { 280 scanf("%d %d", &n, &x); 281 for(int i = 0; i < n; ++i){ 282 scanf("%d", a + i); 283 pos[a[i]].push_back(i); 284 prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i])); 285 } 286 287 int p = 1; 288 int lst = n + 5; 289 for(int i = x; i >= 1; --i){ 290 if(pos[i].empty()){ 291 p = i; 292 continue; 293 } 294 if(pos[i].back() > lst) break; 295 p = i; 296 lst = pos[i][0]; 297 } 298 299 long long res = 0; 300 lst = -1; 301 for(int l = 1; l <= x; ++l){ 302 int r = max(l, p - 1); 303 if(lst != -1) r = max(r, prefMax[lst]); 304 res += x - r + 1; 305 if(!pos[l].empty()){ 306 if(pos[l][0] < lst) break; 307 lst = pos[l].back(); 308 } 309 } 310 311 cout << res << endl; 312 return 0; 313 } 314 ``` 315 316 [1167F - Scalar Queries](/contest/1167/problem/F "Educational Codeforces Round 65 (Rated for Div. 2)") 317 318 Idea: [adedalic](/profile/adedalic "International Master adedalic") 319 320 **Tutorial** 321 322 Tutorial is loading... 323 324 **Solution (adedalic)** 325 326 ``` 327 #include<bits/stdc++.h> 328 using namespace std; 329 330 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 331 #define sz(a) int((a).size()) 332 333 typedef long long li; 334 335 const int MOD = int(1e9) + 7; 336 337 int add(int a, int b) { 338 a += b; 339 while(a >= MOD) 340 a -= MOD; 341 while(a < 0) 342 a += MOD; 343 return a; 344 } 345 int mul(int a, int b) { 346 return int(a * 1ll * b % MOD); 347 } 348 349 int n; 350 vector<int> a; 351 352 inline bool read() { 353 if(!(cin >> n)) 354 return false; 355 a.resize(n); 356 fore(i, 0, n) 357 cin >> a[i]; 358 return true; 359 } 360 361 vector<li> f; 362 void inc(int pos, int val) { 363 for(; pos < sz(f); pos |= pos + 1) 364 f[pos] += val; 365 } 366 li sum(int pos) { 367 li ans = 0; 368 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 369 ans += f[pos]; 370 return ans; 371 } 372 373 vector<int> S[2]; 374 375 inline void solve() { 376 fore(k, 0, 2) { 377 S[k].assign(n, 0); 378 f.assign(n, 0); 379 380 vector<int> dx(a.begin(), a.end()); 381 sort(dx.begin(), dx.end()); 382 383 fore(i, 0, n) { 384 int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin()); 385 S[k][i] = int(sum(pos) % MOD); 386 inc(pos, i + 1); 387 } 388 reverse(a.begin(), a.end()); 389 } 390 391 reverse(S[1].begin(), S[1].end()); 392 int ans = 0; 393 fore(i, 0, n) 394 ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 1))))); 395 396 cout << ans << endl; 397 } 398 399 int main() { 400 #ifdef _DEBUG 401 freopen("input.txt", "r", stdin); 402 int tt = clock(); 403 #endif 404 ios_base::sync_with_stdio(false); 405 cin.tie(0), cout.tie(0); 406 407 if(read()) { 408 solve(); 409 410 #ifdef _DEBUG 411 cerr << "TIME = " << clock() - tt << endl; 412 tt = clock(); 413 #endif 414 } 415 return 0; 416 } 417 ``` 418 419 [1167G - Low Budget Inception](/contest/1167/problem/G "Educational Codeforces Round 65 (Rated for Div. 2)") 420 421 Idea: [adedalic](/profile/adedalic "International Master adedalic") 422 423 **Tutorial** 424 425 Tutorial is loading... 426 427 **Solution (adedalic)** 428 429 ``` 430 #include<bits/stdc++.h> 431 432 using namespace std; 433 434 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 435 #define sz(a) int((a).size()) 436 437 #define x first 438 #define y second 439 440 typedef long long li; 441 442 const int INF = int(1e9); 443 const li INF64 = li(1e18); 444 445 const int N = 200 * 1000 + 555; 446 const int D = 7077; 447 448 int n, d, m; 449 int a[N], qs[N]; 450 451 inline bool read() { 452 if(scanf("%d%d", &n, &d) != 2) 453 return false; 454 fore(i, 0, n) 455 scanf("%d", &a[i]); 456 457 assert(scanf("%d", &m) == 1); 458 fore(i, 0, m) 459 scanf("%d", &qs[i]); 460 return true; 461 } 462 463 bitset<D> L, R, cur; 464 int dist[N]; 465 set<int> has; 466 467 void shiftL(int s, int t, int &uk) { 468 L <<= t - s; 469 for(; uk < n && a[uk] < t; uk++) { 470 if(t - a[uk] - 1 < D) 471 L[t - a[uk] - 1] = 1; 472 if(t - a[uk] < D) 473 L[t - a[uk]] = 1; 474 } 475 } 476 477 void shiftR(int s, int t, int &uk) { 478 R >>= t - s; 479 if(!has.count(t)) 480 R[0] = 0; 481 482 for(; uk < n && a[uk] < t + D; uk++) { 483 if(a[uk] - t >= 0) { 484 R[a[uk] - t] = 1; 485 if(a[uk] - t + 1 >= 0) 486 R[a[uk] - t + 1] = 1; 487 } 488 } 489 } 490 491 inline void solve() { 492 fore(i, 0, m) { 493 dist[i] = INF; 494 int pos = int(lower_bound(a, a + n, qs[i]) - a); 495 if(pos > 0) 496 dist[i] = qs[i] - a[pos - 1] - 1; 497 if(pos < n) 498 dist[i] = min(dist[i], a[pos] - qs[i]); 499 } 500 has = set<int>(a, a + n); 501 502 int uL = 0, uR = 0; 503 L.reset(); 504 R.reset(); 505 fore(i, 0, m) { 506 shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL); 507 shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR); 508 509 double ans = atan2(1, dist[i]); 510 511 cur = L & R; 512 int pos = (int)cur._Find_first(); 513 if(pos < D) { 514 int ds = pos; 515 ans = max(ans, 2 * atan2(1, ds)); 516 } 517 printf("%.15f\n", ans); 518 } 519 } 520 521 int main() { 522 #ifdef _DEBUG 523 freopen("input.txt", "r", stdin); 524 int tt = clock(); 525 #endif 526 cout << fixed << setprecision(15); 527 528 if(read()) { 529 solve(); 530 531 #ifdef _DEBUG 532 cerr << "TIME = " << clock() - tt << endl; 533 tt = clock(); 534 #endif 535 } 536 return 0; 537 } 538 ```