1728.md (8929B)
1 Source: https://codeforces.com/blog/entry/106805 2 3 [1728A - Colored Balls: Revisited](/contest/1728/problem/A "Educational Codeforces Round 135 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int n; 23 cin >> n; 24 vector<int> a(n); 25 for (int &x : a) cin >> x; 26 cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n'; 27 } 28 } 29 ``` 30 31 [1728B - Best Permutation](/contest/1728/problem/B "Educational Codeforces Round 135 (Rated for Div. 2)") 32 33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (Neon)** 40 41 ``` 42 #include <bits/stdc++.h> 43 44 using namespace std; 45 46 int main() { 47 int t; 48 cin >> t; 49 while (t--) { 50 int n; 51 cin >> n; 52 vector<int> p(n); 53 iota(p.begin(), p.end(), 1); 54 for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]); 55 for (int &x : p) cout << x << ' '; 56 cout << '\n'; 57 } 58 } 59 ``` 60 61 [1728C - Digital Logarithm](/contest/1728/problem/C "Educational Codeforces Round 135 (Rated for Div. 2)") 62 63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution (awoo)** 70 71 ``` 72 #include <bits/stdc++.h> 73 74 #define forn(i, n) for (int i = 0; i < int(n); i++) 75 76 using namespace std; 77 78 int main() { 79 int t; 80 scanf("%d", &t); 81 forn(_, t){ 82 int n; 83 scanf("%d", &n); 84 vector<int> a(n), b(n); 85 forn(i, n) scanf("%d", &a[i]); 86 forn(i, n) scanf("%d", &b[i]); 87 priority_queue<int> qa(a.begin(), a.end()); 88 priority_queue<int> qb(b.begin(), b.end()); 89 int ans = 0; 90 while (!qa.empty()){ 91 if (qa.top() == qb.top()){ 92 qa.pop(); 93 qb.pop(); 94 continue; 95 } 96 ++ans; 97 if (qa.top() > qb.top()){ 98 qa.push(to_string(qa.top()).size()); 99 qa.pop(); 100 } 101 else{ 102 qb.push(to_string(qb.top()).size()); 103 qb.pop(); 104 } 105 } 106 printf("%d\n", ans); 107 } 108 return 0; 109 } 110 ``` 111 112 [1728D - Letter Picking](/contest/1728/problem/D "Educational Codeforces Round 135 (Rated for Div. 2)") 113 114 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 115 116 **Tutorial** 117 118 Tutorial is loading... 119 120 **Solution (awoo)** 121 122 ``` 123 #include <bits/stdc++.h> 124 125 #define forn(i, n) for (int i = 0; i < int(n); i++) 126 127 using namespace std; 128 129 int comp(char c, char d){ 130 return c < d ? -1 : (c > d ? 1 : 0); 131 } 132 133 int main() { 134 int t; 135 cin >> t; 136 forn(_, t){ 137 string s; 138 cin >> s; 139 int n = s.size(); 140 vector<vector<int>> dp(n + 1, vector<int>(n + 1)); 141 for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){ 142 int r = l + len; 143 dp[l][r] = 1; 144 { 145 int res = -1; 146 if (dp[l + 1][r - 1] != 0) 147 res = max(res, dp[l + 1][r - 1]); 148 else 149 res = max(res, comp(s[l], s[r - 1])); 150 if (dp[l + 2][r] != 0) 151 res = max(res, dp[l + 2][r]); 152 else 153 res = max(res, comp(s[l], s[l + 1])); 154 dp[l][r] = min(dp[l][r], res); 155 } 156 { 157 int res = -1; 158 if (dp[l + 1][r - 1] != 0) 159 res = max(res, dp[l + 1][r - 1]); 160 else 161 res = max(res, comp(s[r - 1], s[l])); 162 if (dp[l][r - 2] != 0) 163 res = max(res, dp[l][r - 2]); 164 else 165 res = max(res, comp(s[r - 1], s[r - 2])); 166 dp[l][r] = min(dp[l][r], res); 167 } 168 } 169 if (dp[0][n] == -1) 170 cout << "Alice\n"; 171 else if (dp[0][n] == 0) 172 cout << "Draw\n"; 173 else 174 cout << "Bob\n"; 175 } 176 return 0; 177 } 178 ``` 179 180 [1728E - Red-Black Pepper](/contest/1728/problem/E "Educational Codeforces Round 135 (Rated for Div. 2)") 181 182 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 183 184 **Tutorial** 185 186 Tutorial is loading... 187 188 **Solution (awoo)** 189 190 ``` 191 #include <bits/stdc++.h> 192 193 #define forn(i, n) for (int i = 0; i < int(n); i++) 194 195 using namespace std; 196 197 long long gcd(long long a, long long b, long long& x, long long& y) { 198 if (b == 0) { 199 x = 1; 200 y = 0; 201 return a; 202 } 203 long long x1, y1; 204 long long d = gcd(b, a % b, x1, y1); 205 x = y1; 206 y = x1 - y1 * (a / b); 207 return d; 208 } 209 210 bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) { 211 g = gcd(abs(a), abs(b), x0, y0); 212 if (c % g) { 213 return false; 214 } 215 x0 *= c / g; 216 y0 *= c / g; 217 if (a < 0) x0 = -x0; 218 if (b < 0) y0 = -y0; 219 return true; 220 } 221 222 int main() { 223 int n; 224 scanf("%d", &n); 225 vector<int> a(n), b(n); 226 forn(i, n) scanf("%d%d", &a[i], &b[i]); 227 long long cur = accumulate(b.begin(), b.end(), 0ll); 228 vector<int> difs(n); 229 forn(i, n) difs[i] = a[i] - b[i]; 230 sort(difs.begin(), difs.end(), greater<int>()); 231 vector<long long> bst(n + 1); 232 forn(i, n + 1){ 233 bst[i] = cur; 234 if (i < n) 235 cur += difs[i]; 236 } 237 int mx = max_element(bst.begin(), bst.end()) - bst.begin(); 238 int m; 239 scanf("%d", &m); 240 forn(_, m){ 241 int x, y; 242 scanf("%d%d", &x, &y); 243 long long x0, y0, g; 244 if (!find_any_solution(x, y, n, x0, y0, g)){ 245 puts("-1"); 246 continue; 247 } 248 long long l = x * 1ll * y / g; 249 long long red = x0 * 1ll * x; 250 red = red + (max(0ll, mx - red) + l - 1) / l * l; 251 red = red - max(0ll, red - mx) / l * l; 252 long long ans = -1; 253 if (red <= n) ans = max(ans, bst[red]); 254 red -= l; 255 if (red >= 0) ans = max(ans, bst[red]); 256 printf("%lld\n", ans); 257 } 258 return 0; 259 } 260 ``` 261 262 [1728F - Fishermen](/contest/1728/problem/F "Educational Codeforces Round 135 (Rated for Div. 2)") 263 264 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 265 266 **Tutorial** 267 268 Tutorial is loading... 269 270 **Solution (BledDest)** 271 272 ``` 273 #include <bits/stdc++.h> 274 275 using namespace std; 276 277 const int N = 1003; 278 279 int n; 280 int a[N]; 281 vector<int> g[N * N]; 282 int mt[N]; 283 bool used[N * N]; 284 vector<int> val; 285 286 bool kuhn(int x) 287 { 288 if(used[x]) return false; 289 used[x] = true; 290 for(auto y : g[x]) 291 if(mt[y] == -1 || kuhn(mt[y])) 292 { 293 mt[y] = x; 294 return true; 295 } 296 return false; 297 } 298 299 int main() 300 { 301 cin >> n; 302 for(int i = 0; i < n; i++) cin >> a[i]; 303 for(int i = 0; i < n; i++) 304 for(int j = 1; j <= n; j++) 305 val.push_back(a[i] * j); 306 sort(val.begin(), val.end()); 307 val.erase(unique(val.begin(), val.end()), val.end()); 308 int v = val.size(); 309 long long ans = 0; 310 for(int i = 0; i < n; i++) 311 for(int j = 1; j <= n; j++) 312 { 313 int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin(); 314 g[k].push_back(i); 315 } 316 for(int i = 0; i < n; i++) mt[i] = -1; 317 for(int i = 0; i < v; i++) 318 { 319 if(kuhn(i)) 320 { 321 ans += val[i]; 322 for(int j = 0; j < v; j++) used[j] = false; 323 } 324 } 325 cout << ans << endl; 326 } 327 ``` 328 329 [1728G - Illumination](/contest/1728/problem/G "Educational Codeforces Round 135 (Rated for Div. 2)") 330 331 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 332 333 **Tutorial** 334 335 Tutorial is loading... 336 337 **Solution (awoo)** 338 339 ``` 340 #include <bits/stdc++.h> 341 342 #define forn(i, n) for (int i = 0; i < int(n); i++) 343 344 using namespace std; 345 346 const int MOD = 998244353; 347 348 int add(int a, int b){ 349 a += b; 350 if (a >= MOD) 351 a -= MOD; 352 if (a < 0) 353 a += MOD; 354 return a; 355 } 356 357 int mul(int a, int b){ 358 return a * 1ll * b % MOD; 359 } 360 361 int binpow(int a, int b){ 362 int res = 1; 363 while (b){ 364 if (b & 1) 365 res = mul(res, a); 366 a = mul(a, a); 367 b >>= 1; 368 } 369 return res; 370 } 371 372 int main() { 373 int D, n, m; 374 375 scanf("%d%d%d", &D, &n, &m); 376 377 vector<int> inv(D + 1); 378 forn(i, D + 1) inv[i] = binpow(i, MOD - 2); 379 380 vector<int> b(n); 381 forn(i, n) scanf("%d", &b[i]); 382 383 vector<int> a(m); 384 forn(i, m) scanf("%d", &a[i]); 385 sort(a.begin(), a.end()); 386 387 int fl = (1 << m) - 1; 388 vector<int> ways(1 << m, 1); 389 forn(i, m) forn(j, n){ 390 int d = abs(b[j] - a[i]); 391 int mask; 392 if (b[j] > a[i]){ 393 int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin(); 394 mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1); 395 } 396 else{ 397 int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin(); 398 mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1); 399 } 400 ways[mask] = mul(ways[mask], d); 401 mask ^= (1 << i); 402 ways[mask] = mul(ways[mask], inv[d]); 403 } 404 405 forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){ 406 ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]); 407 } 408 409 ways[0] = binpow(D + 1, n); 410 forn(mask, 1 << m){ 411 ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1); 412 } 413 forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){ 414 ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]); 415 } 416 417 int q; 418 scanf("%d", &q); 419 forn(_, q){ 420 int x; 421 scanf("%d", &x); 422 int ans = binpow(D + 1, n + 1); 423 forn(i, m){ 424 int d = abs(x - a[i]); 425 int mask; 426 if (x > a[i]){ 427 int r = lower_bound(a.begin(), a.end(), x + d) - a.begin(); 428 mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1); 429 } 430 else{ 431 int l = lower_bound(a.begin(), a.end(), x - d) - a.begin(); 432 mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1); 433 } 434 ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d)); 435 } 436 printf("%d\n", ans); 437 } 438 439 return 0; 440 } 441 ```