1257.md (9271B)
1 Source: https://codeforces.com/blog/entry/71434 2 3 [1257A - Two Rival Students](/contest/1257/problem/A "Educational Codeforces Round 76 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 import kotlin.math.abs 15 fun main() { 16 val q = readLine()!!.toInt() 17 for (ct in 1..q) { 18 val (n, x, a, b) = readLine()!!.split(' ').map { it.toInt() } 19 println(minOf(n - 1, abs(a - b) + x)) 20 } 21 } 22 ``` 23 24 [1257B - Magic Stick](/contest/1257/problem/B "Educational Codeforces Round 76 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (Ne0n25)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 void solve() { 40 int x, y; 41 cin >> x >> y; 42 43 if (x > 3) puts("YES"); 44 else if (x == 1) puts(y == 1 ? "YES" : "NO"); 45 else puts(y <= 3 ? "YES" : "NO"); 46 } 47 48 int main() { 49 int tc; 50 cin >> tc; 51 while (tc--) solve(); 52 } 53 ``` 54 55 [1257C - Dominated Subarray](/contest/1257/problem/C "Educational Codeforces Round 76 (Rated for Div. 2)") 56 57 Idea: [adedalic](/profile/adedalic "International Master adedalic") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution (adedalic)** 64 65 ``` 66 #include<bits/stdc++.h> 67 using namespace std; 68 69 #define sz(a) int((a).size()) 70 71 int n; 72 vector<int> a; 73 74 inline bool read() { 75 if(!(cin >> n)) 76 return false; 77 a.resize(n); 78 for(int i = 0; i < n; i++) 79 cin >> a[i]; 80 return true; 81 } 82 83 inline void solve() { 84 int ans = n + 5; 85 vector<int> lst(n + 1, -1); 86 for(int i = 0; i < n; i++) { 87 if(lst[a[i]] != -1) 88 ans = min(ans, i - lst[a[i]] + 1); 89 lst[a[i]] = i; 90 } 91 if(ans > n) 92 ans = -1; 93 cout << ans << endl; 94 } 95 96 int main() { 97 #ifdef _DEBUG 98 freopen("input.txt", "r", stdin); 99 #endif 100 ios_base::sync_with_stdio(false); 101 cin.tie(0), cout.tie(0); 102 cout << fixed << setprecision(15); 103 104 int tc; cin >> tc; 105 while(tc--) { 106 assert(read()); 107 solve(); 108 } 109 return 0; 110 } 111 ``` 112 113 [1257D - Yet Another Monster Killing Problem](/contest/1257/problem/D "Educational Codeforces Round 76 (Rated for Div. 2)") 114 115 Idea: [Roms](/profile/Roms "Master Roms") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution (Roms)** 122 123 ``` 124 #include <bits/stdc++.h> 125 126 using namespace std; 127 128 const int N = int(2e5) + 99; 129 130 int t; 131 int n; 132 int a[N]; 133 int m; 134 int p[N], s[N]; 135 int bst[N]; 136 137 int main() { 138 scanf("%d", &t); 139 for(int tc = 0; tc < t; ++tc){ 140 scanf("%d", &n); 141 for(int i = 0; i <= n; ++i) bst[i] = 0; 142 for(int i = 0; i < n; ++i) 143 scanf("%d", a + i); 144 scanf("%d", &m); 145 for(int i = 0; i < m; ++i){ 146 scanf("%d %d", p + i, s + i); 147 bst[s[i]] = max(bst[s[i]], p[i]); 148 } 149 for(int i = n - 1; i >= 0; --i) 150 bst[i] = max(bst[i], bst[i + 1]); 151 152 153 int pos = 0; 154 int res = 0; 155 bool ok = true; 156 while(pos < n){ 157 ++res; 158 int npos = pos; 159 int mx = 0; 160 while(true){ 161 mx = max(mx, a[npos]); 162 if(mx > bst[npos - pos + 1]) break; 163 ++npos; 164 } 165 166 if(pos == npos){ 167 ok = false; 168 break; 169 } 170 pos = npos; 171 } 172 173 if(!ok) res = -1; 174 printf("%d\n", res); 175 } 176 177 return 0; 178 } 179 ``` 180 181 [1257E - The Contest](/contest/1257/problem/E "Educational Codeforces Round 76 (Rated for Div. 2)") 182 183 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Solution (BledDest)** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 using namespace std; 195 196 int main() 197 { 198 int k1, k2, k3; 199 scanf("%d %d %d", &k1, &k2, &k3); 200 int n = k1 + k2 + k3; 201 vector<int> a(n); 202 for(int i = 0; i < k1; i++) 203 { 204 int x; 205 scanf("%d", &x); 206 a[x - 1] = 0; 207 } 208 for(int i = 0; i < k2; i++) 209 { 210 int x; 211 scanf("%d", &x); 212 a[x - 1] = 1; 213 } 214 for(int i = 0; i < k3; i++) 215 { 216 int x; 217 scanf("%d", &x); 218 a[x - 1] = 2; 219 } 220 221 int ans = 0; 222 int bestp = 0; 223 for(int i = 0; i < n; i++) 224 if(a[i] != 2) 225 ans++; 226 vector<int> cntl(3); 227 vector<int> cntr(3); 228 for(int i = 0; i < n; i++) 229 cntr[a[i]]++; 230 for(int i = 0; i < n; i++) 231 { 232 cntl[a[i]]++; 233 cntr[a[i]]--; 234 bestp = max(bestp, cntl[0] - cntl[1]); 235 int curans = cntr[0] + cntr[1] + cntl[2] + cntl[0] - bestp; 236 ans = min(ans, curans); 237 } 238 239 cout << ans << endl; 240 } 241 ``` 242 243 [1257F - Make Them Similar](/contest/1257/problem/F "Educational Codeforces Round 76 (Rated for Div. 2)") 244 245 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 246 247 **Tutorial** 248 249 Tutorial is loading... 250 251 **Solution (BledDest)** 252 253 ``` 254 #include<bits/stdc++.h> 255 256 using namespace std; 257 258 typedef long long li; 259 const int N = 143; 260 const int K = 15; 261 const int V = 5000000; 262 263 int n; 264 li a[N]; 265 int lst[V]; 266 map<int, int> nxt[V]; 267 int t = 1; 268 li a1[N]; 269 li a2[N]; 270 271 int get_nxt(int v, int x) 272 { 273 if(!nxt[v].count(x)) 274 nxt[v][x] = t++; 275 return nxt[v][x]; 276 } 277 278 void add(vector<int> diff, int x) 279 { 280 int v = 0; 281 for(auto i : diff) 282 v = get_nxt(v, i); 283 lst[v] = x; 284 } 285 286 int try_find(vector<int> diff) 287 { 288 int v = 0; 289 for(auto i : diff) 290 { 291 if(!nxt[v].count(i)) 292 return -1; 293 v = nxt[v][i]; 294 } 295 return lst[v]; 296 } 297 298 vector<int> get_diff(li arr[N], int x) 299 { 300 vector<int> cnt(n); 301 for(int i = 0; i < n; i++) 302 cnt[i] = __builtin_popcountll(arr[i] ^ x); 303 vector<int> diff(n - 1); 304 for(int i = 0; i + 1 < n; i++) 305 diff[i] = cnt[i + 1] - cnt[0]; 306 return diff; 307 } 308 309 int main() 310 { 311 cin >> n; 312 for(int i = 0; i < n; i++) 313 cin >> a[i]; 314 315 for(int i = 0; i < n; i++) 316 { 317 a1[i] = (a[i] >> K); 318 a2[i] = a[i] ^ (a1[i] << K); 319 } 320 for(int i = 0; i < (1 << K); i++) 321 { 322 vector<int> d = get_diff(a1, i); 323 add(d, i); 324 } 325 for(int i = 0; i < (1 << K); i++) 326 { 327 vector<int> d = get_diff(a2, i); 328 for(int j = 0; j + 1 < n; j++) 329 d[j] *= -1; 330 int x = try_find(d); 331 if(x != -1) 332 { 333 li res = (li(x) << K) ^ i; 334 cout << res << endl; 335 return 0; 336 } 337 } 338 cout << -1 << endl; 339 return 0; 340 return 0; 341 } 342 ``` 343 344 [1257G - Divisor Set](/contest/1257/problem/G "Educational Codeforces Round 76 (Rated for Div. 2)") 345 346 Idea: [adedalic](/profile/adedalic "International Master adedalic") 347 348 **Tutorial** 349 350 Tutorial is loading... 351 352 **Solution (adedalic)** 353 354 ``` 355 #include<bits/stdc++.h> 356 357 using namespace std; 358 359 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 360 #define sz(a) int((a).size()) 361 362 const int LOGN = 18; 363 const int MOD = 998244353; 364 int g = 3; 365 366 int mul(int a, int b) { 367 return int(a * 1ll * b % MOD); 368 } 369 int norm(int a) { 370 while(a >= MOD) a -= MOD; 371 while(a < 0) a += MOD; 372 return a; 373 } 374 int binPow (int a, int k) { 375 int ans = 1; 376 for (; k > 0; k >>= 1) { 377 if (k & 1) 378 ans = mul(ans, a); 379 a = mul(a, a); 380 } 381 return ans; 382 } 383 int inv(int a) { 384 return binPow(a, MOD - 2); 385 } 386 387 vector<int> w[LOGN], rv; 388 bool precalced = false; 389 390 void precalc() { 391 if(precalced) 392 return; 393 precalced = true; 394 395 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 396 fore(st, 0, LOGN) { 397 w[st].assign(1 << st, 1); 398 399 int bw = binPow(wb, 1 << (LOGN - st - 1)); 400 int cw = 1; 401 402 fore(k, 0, (1 << st)) { 403 w[st][k] = cw; 404 cw = mul(cw, bw); 405 } 406 } 407 408 rv.assign(1 << LOGN, 0); 409 fore(i, 1, sz(rv)) 410 rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1)); 411 } 412 413 const int MX = (1 << LOGN) + 3; 414 415 inline void fft(int a[MX], int n, bool inverse) { 416 precalc(); 417 418 int ln = __builtin_ctz(n); 419 assert((1 << ln) < MX); 420 assert((1 << ln) == n); 421 422 fore(i, 0, n) { 423 int ni = rv[i] >> (LOGN - ln); 424 if(i < ni) swap(a[i], a[ni]); 425 } 426 427 for(int st = 0; (1 << st) < n; st++) { 428 int len = (1 << st); 429 for(int k = 0; k < n; k += (len << 1)) { 430 fore(pos, k, k + len) { 431 int l = a[pos]; 432 int r = mul(a[pos + len], w[st][pos - k]); 433 434 a[pos] = norm(l + r); 435 a[pos + len] = norm(l - r); 436 } 437 } 438 } 439 440 if(inverse) { 441 int in = inv(n); 442 fore(i, 0, n) 443 a[i] = mul(a[i], in); 444 reverse(a + 1, a + n); 445 } 446 } 447 448 int aa[MX], bb[MX], cc[MX]; 449 450 vector<int> multiply(const vector<int> &a, const vector<int> &b) { 451 int ln = 1; 452 while(ln < (sz(a) + sz(b))) 453 ln <<= 1; 454 455 fore(i, 0, ln) 456 aa[i] = (i < sz(a) ? a[i] : 0); 457 fore(i, 0, ln) 458 bb[i] = (i < sz(b) ? b[i] : 0); 459 460 fft(aa, ln, false); 461 fft(bb, ln, false); 462 463 fore(i, 0, ln) 464 cc[i] = mul(aa[i], bb[i]); 465 fft(cc, ln, true); 466 467 vector<int> ans(cc, cc + ln); 468 while(ans.back() == 0) 469 ans.pop_back(); 470 return ans; 471 } 472 473 int n; 474 vector<int> ps; 475 476 inline bool read() { 477 if(!(cin >> n)) 478 return false; 479 ps.resize(n); 480 fore(i, 0, n) 481 cin >> ps[i]; 482 return true; 483 } 484 485 struct cmp { 486 bool operator ()(const vector<int> &a, const vector<int> &b) { 487 return sz(a) < sz(b); 488 } 489 }; 490 491 inline void solve() { 492 map<int, int> cnt; 493 fore (i, 0, n) 494 cnt[ps[i]]++; 495 496 multiset< vector<int>, cmp > polys; 497 for (auto p : cnt) 498 polys.emplace(p.second + 1, 1); 499 500 while (sz(polys) > 1) { 501 auto it2 = polys.begin(); 502 auto it1 = it2++; 503 polys.insert(multiply(*it1, *it2)); 504 505 polys.erase(it1); 506 polys.erase(it2); 507 } 508 509 auto poly = *polys.begin(); 510 // cerr << '['; 511 // fore(i, 0, sz(poly)) { 512 // if(i) cerr << ", "; 513 // cerr << poly[i]; 514 // } 515 // cerr << ']' << endl; 516 517 cout << poly[n / 2] << endl; 518 } 519 520 int main() { 521 #ifdef _DEBUG 522 freopen("input.txt", "r", stdin); 523 int tt = clock(); 524 #endif 525 ios_base::sync_with_stdio(false); 526 cin.tie(0), cout.tie(0); 527 cout << fixed << setprecision(15); 528 529 if(read()) { 530 solve(); 531 532 #ifdef _DEBUG 533 cerr << "TIME = " << clock() - tt << endl; 534 tt = clock(); 535 #endif 536 } 537 return 0; 538 } 539 ```