1879.md (8682B)
1 Source: https://codeforces.com/blog/entry/120773 2 3 [1879A - Rigged!](/contest/1879/problem/A "Educational Codeforces Round 155 (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 const int N = 109; 19 20 int t; 21 int n; 22 int s[N], e[N]; 23 24 int main() { 25 cin >> t; 26 for (int tc = 0; tc < t; ++tc) { 27 cin >> n; 28 for (int i = 0; i < n; ++i) { 29 cin >> s[i] >> e[i]; 30 } 31 32 bool ok = true; 33 for (int i = 1; i < n; ++i) 34 if (s[i] >= s[0] && e[i] >= e[0]) 35 ok = false; 36 37 if (!ok) { 38 puts("-1"); 39 continue; 40 } 41 42 cout << s[0] << endl; 43 } 44 return 0; 45 } 46 ``` 47 48 [1879B - Chips on the Board](/contest/1879/problem/B "Educational Codeforces Round 155 (Rated for Div. 2)") 49 50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Solution (Neon)** 57 58 ``` 59 #include <bits/stdc++.h> 60 61 using namespace std; 62 63 using li = long long; 64 65 int main() { 66 ios::sync_with_stdio(false); cin.tie(0); 67 int t; 68 cin >> t; 69 while (t--) { 70 int n; 71 cin >> n; 72 vector<li> a(n), b(n); 73 for (auto& x : a) cin >> x; 74 for (auto& x : b) cin >> x; 75 li mnA = *min_element(a.begin(), a.end()); 76 li sA = accumulate(a.begin(), a.end(), 0LL); 77 li mnB = *min_element(b.begin(), b.end()); 78 li sB = accumulate(b.begin(), b.end(), 0LL); 79 li ans = min(mnA * n + sB, mnB * n + sA); 80 cout << ans << '\n'; 81 } 82 } 83 ``` 84 85 [1879C - Make it Alternating](/contest/1879/problem/C "Educational Codeforces Round 155 (Rated for Div. 2)") 86 87 Idea: [Roms](/profile/Roms "Master Roms") 88 89 **Tutorial** 90 91 Tutorial is loading... 92 93 **Solution (Roms)** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 const int MOD = 998'244'353; 101 102 void upd(int &a, int b) { 103 a = (a * 1LL * b) % MOD; 104 } 105 106 int t; 107 string s; 108 109 int main() { 110 cin >> t; 111 for (int tc = 0; tc < t; ++tc) { 112 cin >> s; 113 int res = 1; 114 int k = s.size(); 115 int n = s.size(); 116 for (int l = 0; l < n; ) { 117 int r = l + 1; 118 while(r < n && s[l] == s[r]) 119 ++r; 120 upd(res, r - l); 121 --k; 122 l = r; 123 } 124 125 for (int i = 1; i <= k; ++i) 126 upd(res, i); 127 cout << k << ' ' << res << endl; 128 } 129 } 130 ``` 131 132 [1879D - Sum of XOR Functions](/contest/1879/problem/D "Educational Codeforces Round 155 (Rated for Div. 2)") 133 134 Idea: [Roms](/profile/Roms "Master Roms") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution (Roms)** 141 142 ``` 143 #include <bits/stdc++.h> 144 145 using namespace std; 146 147 const int N = 300005; 148 const int MOD = 998244353; 149 int n; 150 int a[N]; 151 152 void add(int &a, int b) { 153 a += b; 154 if (a >= MOD) 155 a -= MOD; 156 } 157 158 int sum(int a, int b) { 159 a += b; 160 if (a >= MOD) 161 a -= MOD; 162 if (a < 0) 163 a += MOD; 164 return a; 165 } 166 167 int mul(int a, int b) { 168 return (a * 1LL * b) % MOD; 169 } 170 171 int main() { 172 cin >> n; 173 for (int i = 0; i < n; ++i) 174 cin >> a[i]; 175 176 int res = 0; 177 for (int b = 0; b < 30; ++b) { 178 int cur = 0; 179 vector <int> cnt(2); 180 vector <int> sumOfL(2); 181 cnt[0] = 1; 182 int x = 0; 183 for (int i = 0; i < n; ++i) { 184 x ^= ((a[i] >> b) & 1); 185 int sumOfR = mul(cnt[x ^ 1], i + 1); 186 add(cur, sum(sumOfR, -sumOfL[x ^ 1])); 187 188 ++cnt[x]; 189 add(sumOfL[x], i + 1); 190 } 191 192 add(res, mul(1 << b, cur)); 193 } 194 195 cout << res << endl; 196 } 197 ``` 198 199 [1879E - Interactive Game with Coloring](/contest/1879/problem/E "Educational Codeforces Round 155 (Rated for Div. 2)") 200 201 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Solution (BledDest)** 208 209 ``` 210 #include<bits/stdc++.h> 211 212 using namespace std; 213 214 const int N = 123; 215 216 int n; 217 int color[N]; 218 int countColors[N][N]; 219 int p[N]; 220 vector<int> g[N]; 221 int deg[N]; 222 223 void add_edge(int x, int y) 224 { 225 g[x].push_back(y); 226 g[y].push_back(x); 227 } 228 229 bool tryTwoColors() 230 { 231 int v1 = n + 1; 232 int v2 = n + 2; 233 for(int i = 2; i <= n; i++) 234 { 235 if(p[i] != 1) 236 { 237 add_edge(i, p[i]); 238 } 239 } 240 for(int i = 2; i <= n; i++) 241 { 242 if(deg[i] == 1) 243 add_edge(i, v1); 244 } 245 for(int i = 2; i <= n; i++) 246 { 247 if(p[i] != 1 && deg[p[i]] == 1) 248 add_edge(i, v2); 249 } 250 add_edge(v1, v2); 251 bool bad = false; 252 for(int i = 2; i <= n + 2; i++) 253 if(color[i] == 0) 254 { 255 color[i] = 1; 256 queue<int> q; 257 q.push(i); 258 while(!q.empty()) 259 { 260 int k = q.front(); 261 q.pop(); 262 for(auto y : g[k]) 263 { 264 if(color[y] == 0) 265 { 266 color[y] = 3 - color[k]; 267 q.push(y); 268 } 269 else if(color[y] == color[k]) 270 bad = true; 271 } 272 } 273 } 274 if(bad) 275 for(int i = 2; i <= n + 2; i++) 276 color[i] = 0; 277 return !bad; 278 } 279 280 void tryThreeColors() 281 { 282 for(int i = 2; i <= n; i++) 283 if(p[i] == 1) 284 color[i] = 1; 285 else 286 color[i] = (color[p[i]] % 3) + 1; 287 } 288 289 int findVertex(const vector<int>& colors) 290 { 291 int s = colors.size(); 292 for(int i = 2; i <= n; i++) 293 { 294 if(vector<int>(countColors[i], countColors[i] + s) == colors) 295 return i; 296 } 297 return -1; 298 } 299 300 int main() 301 { 302 cin >> n; 303 for(int i = 2; i <= n; i++) 304 { 305 cin >> p[i]; 306 deg[p[i]]++; 307 } 308 309 if(*max_element(p + 2, p + n + 1) == 1) 310 { 311 for(int i = 2; i <= n; i++) 312 color[i] = 1; 313 } 314 else if (!tryTwoColors()) 315 tryThreeColors(); 316 317 int colorsUsed = *max_element(color + 2, color + n + 1); 318 319 cout << colorsUsed << endl; 320 for(int i = 2; i <= n; i++) 321 { 322 cout << color[i]; 323 if(i == n) cout << endl; 324 else cout << " "; 325 } 326 cout.flush(); 327 328 for(int i = 2; i <= n; i++) 329 { 330 countColors[i][color[i]]++; 331 countColors[p[i]][color[i]]++; 332 } 333 334 while(true) 335 { 336 int resp; 337 cin >> resp; 338 if(resp == -1 || resp == 1) 339 exit(0); 340 vector<int> counts(colorsUsed + 1); 341 for(int i = 1; i <= colorsUsed; i++) 342 cin >> counts[i]; 343 int v = findVertex(counts); 344 assert(v != -1); 345 cout << color[v] << endl; 346 cout.flush(); 347 } 348 } 349 ``` 350 351 [1879F - Last Man Standing](/contest/1879/problem/F "Educational Codeforces Round 155 (Rated for Div. 2)") 352 353 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 354 355 **Tutorial** 356 357 Tutorial is loading... 358 359 **Solution (awoo)** 360 361 ``` 362 #include <bits/stdc++.h> 363 364 #define forn(i, n) for (int i = 0; i < int(n); i++) 365 366 using namespace std; 367 368 int main() { 369 int t; 370 scanf("%d", &t); 371 while (t--){ 372 int n; 373 scanf("%d", &n); 374 vector<int> h(n), a(n); 375 forn(i, n) scanf("%d", &h[i]); 376 forn(i, n) scanf("%d", &a[i]); 377 int mxa = *max_element(a.begin(), a.end()) + 1; 378 379 int l = mxa == 1 ? 0 : (__lg(mxa - 1) + 1); 380 vector<vector<pair<int, int>>> st(l, vector<pair<int, int>>(mxa, make_pair(0, -1))); 381 vector<vector<int>> st2(l, vector<int>(mxa)); 382 forn(i, n){ 383 if (h[i] > st[0][a[i]].first){ 384 st2[0][a[i]] = st[0][a[i]].first; 385 st[0][a[i]] = {h[i], i}; 386 } 387 else if (h[i] > st2[0][a[i]]){ 388 st2[0][a[i]] = h[i]; 389 } 390 } 391 392 auto combine = [&st, &st2](int i, int x, int y){ 393 int mx = max(st[i][x].first, st[i][y].first); 394 if (mx == st[i][x].first) 395 return max(st2[i][x], st[i][y].first); 396 return max(st[i][x].first, st2[i][y]); 397 }; 398 399 for (int j = 1; j < l; ++j) forn(i, mxa){ 400 if (i + (1 << (j - 1)) < mxa){ 401 st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]); 402 st2[j][i] = combine(j - 1, i, i + (1 << (j - 1))); 403 } 404 else{ 405 st[j][i] = st[j - 1][i]; 406 st2[j][i] = st2[j - 1][i]; 407 } 408 } 409 vector<int> pw(mxa + 1); 410 for (int i = 2; i <= mxa; ++i) pw[i] = pw[i / 2] + 1; 411 412 auto getmx = [&st, &pw](int l, int r){ 413 int len = pw[r - l]; 414 return max(st[len][l], st[len][r - (1 << len)]); 415 }; 416 auto getmx2 = [&st, &st2, &pw, &combine](int l, int r){ 417 int len = pw[r - l]; 418 if (st[len][l].second != st[len][r - (1 << len)].second) 419 return combine(len, l, r - (1 << len)); 420 return max(st2[len][l], st2[len][r - (1 << len)]); 421 }; 422 423 vector<long long> svmx(mxa), svmx2(mxa); 424 vector<int> svwho(mxa, -1); 425 for (int x = 1; x < mxa; ++x){ 426 for (int l = 1; l < mxa; l += x){ 427 int r = min(mxa, l + x); 428 int ac = (l - 1) / x + 1; 429 auto tmp = getmx(l, r); 430 long long mx = tmp.first * 1ll * ac; 431 int who = tmp.second; 432 long long mx2 = getmx2(l, r) * 1ll * ac; 433 if (who == -1) continue; 434 if (mx > svmx[x]){ 435 svmx2[x] = svmx[x]; 436 svmx[x] = mx; 437 svwho[x] = who; 438 } 439 else if (mx > svmx2[x]){ 440 svmx2[x] = mx; 441 } 442 svmx2[x] = max(svmx2[x], mx2); 443 } 444 } 445 446 vector<long long> ans(n); 447 forn(i, mxa) if (svwho[i] != -1) 448 ans[svwho[i]] = max(ans[svwho[i]], svmx[i] - svmx2[i]); 449 450 forn(i, n) printf("%lld ", ans[i]); 451 puts(""); 452 } 453 return 0; 454 } 455 ```