2209.md (10132B)
1 Source: https://codeforces.com/blog/entry/152272 2 3 We hope you enjoyed the problems! 4 5 **Rate the contest!** 6 7 **Quality** 8 9 * Excellent contest 10 * Good contest 11 * Average contest 12 * Bad contest 13 * Horrible contest 14 15 **Difficulty** 16 17 * Trivial contest 18 * Easy contest 19 * Average contest 20 * Hard contest 21 * Impossible contest 22 23 [2209A - Flip Flops](/contest/2209/problem/A "Codeforces Round 1087 (Div. 2)") 24 25 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ") 26 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ") 27 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ") 28 29 **Solution** 30 31 Tutorial is loading... 32 33 **Code (C++)** 34 35 ``` 36 #include<bits/stdc++.h> 37 using namespace std; 38 int n,a[109],k; 39 long long C; 40 int main(){ 41 int t; 42 scanf("%d",&t); 43 while(t--){ 44 scanf("%d %lld %d",&n,&C,&k); 45 for(int i = 1; i <= n; i ++){ 46 scanf("%d",&a[i]); 47 } 48 sort(a + 1,a + n + 1); 49 for(int i = 1; i <= n; i ++){ 50 if(a[i] > C) 51 break; 52 int o = min(1ll * k,C - a[i]); 53 k -= o; 54 C += a[i] + o; 55 } 56 printf("%lld\n",C); 57 } 58 } 59 ``` 60 61 **Rate the problem!** 62 63 **Quality** 64 65 * Excellent problem 66 * Good problem 67 * Average problem 68 * Bad problem 69 * Horrible problem 70 71 **Difficulty** 72 73 * Trivial problem 74 * Easy problem 75 * Average problem 76 * Hard problem 77 * Impossible problem 78 79 [2209B - Array](/contest/2209/problem/B "Codeforces Round 1087 (Div. 2)") 80 81 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ") 82 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ") 83 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ") 84 85 **Solution** 86 87 Tutorial is loading... 88 89 **Code (Python)** 90 91 ``` 92 for _ in range(int(input())): 93 n = int(input()) 94 a = list(map(int, input().split())) 95 print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)]) 96 ``` 97 98 **Code (C++)** 99 100 ``` 101 #include<bits/stdc++.h> 102 using namespace std; 103 int n,a[5009],bcnt,f1[5009],f2[5009]; 104 int main(){ 105 int t; 106 scanf("%d",&t); 107 while(t--){ 108 scanf("%d",&n); 109 for(int i = 1; i <= n; i ++){ 110 scanf("%d",&a[i]); 111 } 112 for(int i = n; i >= 1; i --){ 113 f1[i] = f2[i] = 0; 114 for(int j = i + 1; j <= n; j ++) 115 f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]); 116 f1[i] = max(f1[i],f2[i]); 117 } 118 for(int i = 1; i < n; i ++) 119 printf("%d ",f1[i]); 120 printf("%d\n",f1[n]); 121 } 122 } 123 ``` 124 125 **Rate the problem!** 126 127 **Quality** 128 129 * Excellent problem 130 * Good problem 131 * Average problem 132 * Bad problem 133 * Horrible problem 134 135 **Difficulty** 136 137 * Trivial problem 138 * Easy problem 139 * Average problem 140 * Hard problem 141 * Impossible problem 142 143 [2209C - Find the Zero](/contest/2209/problem/C "Codeforces Round 1087 (Div. 2)") 144 145 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 146 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 147 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 148 149 **Solution** 150 151 Tutorial is loading... 152 153 **Code (Python)** 154 155 ``` 156 for _ in range(int(input())): 157 n = int(input()) 158 ans = -1 159 for i in range(1, n): 160 print("?", 2 * i + 1, 2 * i + 2, flush=True) 161 if int(input()): 162 ans = 2 * i + 1 163 break 164 else: 165 print("?", 1, 3, flush=True) 166 if int(input()): 167 ans = 1 168 else: 169 print("?", 1, 4, flush=True) 170 if int(input()): 171 ans = 1 172 else: 173 ans = 2 174 print("!", ans, flush=True) 175 ``` 176 177 **Rate the problem!** 178 179 **Quality** 180 181 * Excellent problem 182 * Good problem 183 * Average problem 184 * Bad problem 185 * Horrible problem 186 187 **Difficulty** 188 189 * Trivial problem 190 * Easy problem 191 * Average problem 192 * Hard problem 193 * Impossible problem 194 195 [2209D - Ghostfires](/contest/2209/problem/D "Codeforces Round 1087 (Div. 2)") 196 197 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ") 198 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ") 199 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ") 200 201 **Solution** 202 203 Tutorial is loading... 204 205 **Code (C++)** 206 207 ``` 208 #include<bits/stdc++.h> 209 using namespace std; 210 int t,r,g,b,rb,gb,rg; 211 int main(){ 212 scanf("%d",&t); 213 while(t--){ 214 scanf("%d %d %d",&r,&g,&b); 215 while(((r > 0) + (g > 0) + (b > 0)) >> 1){ 216 if(r <= g && r <= b) 217 gb ++,g --,b --; 218 else if(g <= r && g <= b) 219 rb ++,r --,b --; 220 else if(b <= r && b <= g) 221 rg ++,r --,g --; 222 } 223 if(g > 0){ 224 putchar('G'); 225 while(rg > 0) 226 putchar('R'),putchar('G'),rg --; 227 bool flg = false; 228 while(gb > 0) 229 putchar('B'),putchar('G'),gb --,flg = true; 230 if(flg){ 231 while(rb > 0) 232 putchar('B'),putchar('R'),rb --; 233 } 234 else{ 235 while(rb > 0) 236 putchar('R'),putchar('B'),rb --; 237 } 238 } 239 else if(r > 0){ 240 putchar('R'); 241 while(rg > 0) 242 putchar('G'),putchar('R'),rg --; 243 bool flg = false; 244 while(rb > 0) 245 putchar('B'),putchar('R'),rb --,flg = true; 246 if(flg){ 247 while(gb > 0) 248 putchar('B'),putchar('G'),gb --; 249 } 250 else{ 251 while(gb > 0) 252 putchar('G'),putchar('B'),gb --; 253 } 254 } 255 else{ 256 if(b > 0) 257 putchar('B'); 258 while(gb > 0) 259 putchar('G'),putchar('B'),gb --; 260 bool flg = false; 261 while(rb > 0) 262 putchar('R'),putchar('B'),rb --,flg = true; 263 if(flg){ 264 while(rg > 0) 265 putchar('R'),putchar('G'),rg --; 266 } 267 else{ 268 while(rg > 0) 269 putchar('G'),putchar('R'),rg --; 270 } 271 } 272 puts(""); 273 } 274 } 275 ``` 276 277 **Rate the problem!** 278 279 **Quality** 280 281 * Excellent problem 282 * Good problem 283 * Average problem 284 * Bad problem 285 * Horrible problem 286 287 **Difficulty** 288 289 * Trivial problem 290 * Easy problem 291 * Average problem 292 * Hard problem 293 * Impossible problem 294 295 [2209E - A Trivial String Problem](/contest/2209/problem/E "Codeforces Round 1087 (Div. 2)") 296 297 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 298 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 299 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__") 300 301 **Solution** 302 303 Tutorial is loading... 304 305 **Code (Python)** 306 307 ``` 308 import sys 309 input = lambda: sys.stdin.readline().strip() 310 def work(s): 311 n = len(s) 312 p = [0] * n 313 b = [0] * n 314 for i in range(1, n): 315 j = p[i - 1] 316 while j and s[i] != s[j]: 317 j = p[j - 1] 318 if s[i] == s[j]: 319 j += 1 320 p[i] = j 321 if j == 0: 322 b[i] = 0 323 elif p[j - 1] == 0: 324 b[i] = j 325 else: 326 b[i] = b[j - 1] 327 ans = 0 328 for i in range(n): 329 p[i] = 0 330 p[i] = p[i - b[i]] + 1 331 ans += p[i] 332 return ans 333 334 for _ in range(int(input())): 335 n, q = map(int, input().split()) 336 s = input() 337 for _ in range(q): 338 l, r = map(int, input().split()) 339 print(work(s[l - 1:r])) 340 ``` 341 342 **Rate the problem!** 343 344 **Quality** 345 346 * Excellent problem 347 * Good problem 348 * Average problem 349 * Bad problem 350 * Horrible problem 351 352 **Difficulty** 353 354 * Trivial problem 355 * Easy problem 356 * Average problem 357 * Hard problem 358 * Impossible problem 359 360 [2209F - Dynamic Values And Maximum Sum](/contest/2209/problem/F "Codeforces Round 1087 (Div. 2)") 361 362 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ") 363 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ") 364 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ") 365 366 **Solution** 367 368 Tutorial is loading... 369 370 **Code (C++)** 371 372 ``` 373 #include<bits/stdc++.h> 374 using namespace std; 375 const int N = 300009; 376 int n,k,t,a[N],tt[N]; 377 long long b[N],ans[N],sum,mxa; 378 struct FLONG{ 379 long long val; 380 int nd; 381 FLONG(long long v = 0,int d = 0): 382 val(v),nd(d) 383 {} 384 bool operator<(const FLONG &b)const{ 385 return val > b.val || (val == b.val && nd < b.nd); 386 } 387 }; 388 set<FLONG>s; 389 set<FLONG> :: iterator o; 390 struct pir{ 391 int to,len; 392 pir(int t = 0,int l = 0): 393 to(t),len(l) 394 {} 395 bool operator<(const pir &b)const{ 396 return len > b.len || (len == b.len && to < b.to); 397 } 398 }mn[N],se[N],lf[N]; 399 vector<int>e[N]; 400 void srh(int v,int fa){ 401 mn[v] = pir(v,0); 402 se[v] = pir(0,~0x3f3f3f3f); 403 lf[v] = pir(0,~0x3f3f3f3f); 404 for(unsigned i = 0; i < e[v].size(); i ++){ 405 if(e[v][i] != fa){ 406 srh(e[v][i],v); 407 pir th = mn[e[v][i]]; 408 th.len ++; 409 if(th < se[v]) 410 swap(th,se[v]); 411 if(se[v] < mn[v]) 412 swap(se[v],mn[v]); 413 } 414 } 415 } 416 void gt1(){ 417 sum = ans[1] = 0; 418 ans[1] += a[1]; 419 for(int i = 2; i <= n; i ++){ 420 b[mn[i].to] += a[i]; 421 tt[i] = mn[i].to; 422 //printf("%d %d\n",i,tt[i]); 423 } 424 s.clear(); 425 for(int i = 2; i <= n; i ++){ 426 s.insert(FLONG(b[i],i)); 427 } 428 o = s.begin(); 429 ans[1] += o -> val; 430 sum += o -> val; 431 for(int i = 1; i < k - 1; i ++){ 432 o ++; 433 ans[1] += o -> val; 434 sum += o -> val; 435 } 436 s.insert(FLONG(-1ll,0)); 437 s.insert(FLONG(-2ll,0)); 438 } 439 void era(int x){ 440 FLONG u = FLONG(b[x],x); 441 if(!(*o < u)){ 442 o ++; 443 sum += o -> val; 444 sum -= b[x]; 445 } 446 s.erase(u); 447 //printf("%d %lld\n",x,sum); 448 } 449 void ins(int x){ 450 FLONG u = FLONG(b[x],x); 451 s.insert(u); 452 if(!(*o < u)){ 453 sum -= o -> val; 454 sum += b[x]; 455 o --; 456 } 457 //printf("%d %lld\n",x,sum); 458 } 459 void stp(int x){ 460 era(tt[x]); 461 b[tt[x]] -= a[x]; 462 ins(tt[x]); 463 tt[x] = 0; 464 } 465 void sett(int x,int ttp){ 466 tt[x] = ttp; 467 era(tt[x]); 468 b[tt[x]] += a[x]; 469 ins(tt[x]); 470 } 471 void srho(int v,int fa){ 472 //printf(" %d %d\n",v,fa); 473 if(fa != 0){ 474 stp(v); 475 era(v); 476 ins(fa); 477 sett(fa,lf[fa].to); 478 ans[v] = sum + a[v]; 479 } 480 for(unsigned i = 0; i < e[v].size(); i ++){ 481 if(e[v][i] != fa){ 482 pir u = lf[fa]; 483 u.len ++; 484 if(mn[v].to == mn[e[v][i]].to) 485 lf[v] = min(u,se[v]); 486 else 487 lf[v] = min(u,mn[v]); 488 srho(e[v][i],v); 489 } 490 } 491 if(fa != 0){ 492 ins(v); 493 sett(v,mn[v].to); 494 stp(fa); 495 era(fa); 496 } 497 } 498 int main(){ 499 scanf("%d",&t); 500 while(t--){ 501 scanf("%d %d",&n,&k); 502 mxa = 0; 503 for(int i = 1; i <= n; i ++){ 504 scanf("%d",&a[i]); 505 mxa = max(mxa,1ll * a[i]); 506 e[i].clear(); 507 b[i] = 0; 508 } 509 for(int i = 1; i < n; i ++){ 510 int u,v; 511 scanf("%d %d",&u,&v); 512 e[u].emplace_back(v); 513 e[v].emplace_back(u); 514 } 515 if(k == 1){ 516 printf("%lld\n",mxa); 517 continue; 518 } 519 lf[0].len = ~0x3f3f3f3f; 520 srh(1,0); 521 gt1(); 522 srho(1,0); 523 for(int i = 1; i <= n; i ++){ 524 mxa = max(mxa,ans[i]); 525 //printf("%lld\n",ans[i]); 526 } 527 printf("%lld\n",mxa); 528 } 529 } 530 ``` 531 532 **Rate the problem!** 533 534 **Quality** 535 536 * Excellent problem 537 * Good problem 538 * Average problem 539 * Bad problem 540 * Horrible problem 541 542 **Difficulty** 543 544 * Trivial problem 545 * Easy problem 546 * Average problem 547 * Hard problem 548 * Impossible problem