1903.md (14740B)
1 Source: https://codeforces.com/blog/entry/122820 2 3 Problems A, B, C, D1 and E were authored by me and [Adam_GS](/profile/Adam_GS "Grandmaster Adam_GS") authored D2 and F. 4 5 [1903A - Halloumi Boxes](/contest/1903/problem/A "Codeforces Round 912 (Div. 2)") 6 7 **Hint** 8 9 If $k$ is greater or equal to $2$ you can always swap adjacent elements. 10 11 **Solution** 12 13 Tutorial is loading... 14 15 **Code (C++)** 16 17 ``` 18 #include <bits/stdc++.h> 19 using namespace std; 20 int main(){ 21 int t; 22 cin>>t; 23 while(t--){ 24 int n,k; 25 cin>>n>>k; 26 int arr[n]; 27 for(int i = 0;i < n;i++){ 28 cin>>arr[i]; 29 } 30 if(is_sorted(arr,arr+n) || k > 1){ 31 cout<<"YES\n"; 32 } 33 else{ 34 cout<<"NO\n"; 35 } 36 } 37 return 0; 38 } 39 ``` 40 41 **Rate this problem** 42 43 Good 44 45 Mid 46 47 Bad 48 49 [1903B - StORage room](/contest/1903/problem/B "Codeforces Round 912 (Div. 2)") 50 51 **Hint** 52 53 Think of each bit independently. 54 55 **Solution** 56 57 Tutorial is loading... 58 59 **Code (C++)** 60 61 ``` 62 #include <bits/stdc++.h> 63 using namespace std; 64 int main(){ 65 ios_base::sync_with_stdio(0); 66 cin.tie(0); 67 int t; 68 cin>>t; 69 while(t--){ 70 int n; 71 cin>>n; 72 int m[n][n]; 73 int arr[n]; 74 for(int i = 0;i < n;i++){ 75 arr[i] = (1<<30) - 1; 76 } 77 for(int i = 0;i < n;i++){ 78 for(int j = 0;j < n;j++){ 79 cin>>m[i][j]; 80 if(i != j){ 81 arr[i] &= m[i][j]; 82 arr[j] &= m[i][j]; 83 } 84 } 85 } 86 bool ok = true; 87 for(int i = 0;i < n;i++){ 88 for(int j = 0;j < n;j++){ 89 if(i != j && (arr[i] | arr[j]) != m[i][j]){ 90 ok = false; 91 } 92 } 93 } 94 if(!ok){ 95 cout<<"NO\n"; 96 } 97 else{ 98 cout<<"YES\n"; 99 for(int i = 0;i < n;i++){ 100 cout<<arr[i]<<" "; 101 } 102 cout<<"\n"; 103 } 104 } 105 } 106 ``` 107 108 **Rate this problem** 109 110 Good 111 112 Mid 113 114 Bad 115 116 [1903C - Theofanis' Nightmare](/contest/1903/problem/C "Codeforces Round 912 (Div. 2)") 117 118 **Hint** 119 120 Think of suffixes. 121 122 **Solution** 123 124 Tutorial is loading... 125 126 **Code (C++)** 127 128 ``` 129 #include <bits/stdc++.h> 130 using namespace std; 131 int main(){ 132 ios_base::sync_with_stdio(0); 133 cin.tie(0); 134 int t; 135 cin>>t; 136 while(t--){ 137 int n; 138 cin>>n; 139 int arr[n]; 140 long long suf[n+1] = {0}; 141 for(int i = 0;i < n;i++){ 142 cin>>arr[i]; 143 } 144 for(int i = n-1;i >= 0;i--){ 145 suf[i] = suf[i+1] + arr[i]; 146 } 147 long long ans = suf[0]; 148 for(int i = 1;i < n;i++){ 149 if(suf[i] > 0){ 150 ans += suf[i]; 151 } 152 } 153 cout<<ans<<"\n"; 154 } 155 } 156 ``` 157 158 **Rate this problem** 159 160 Good 161 162 Mid 163 164 Bad 165 166 [1903D1 - Maximum And Queries (easy version)](/contest/1903/problem/D1 "Codeforces Round 912 (Div. 2)") 167 168 **Hint** 169 170 Try using greedy to construct the answer bit by bit. 171 172 **Solution** 173 174 Tutorial is loading... 175 176 **Code (C++)** 177 178 ``` 179 #include<bits/stdc++.h> 180 using namespace std; 181 typedef long long ll; 182 typedef long double ld; 183 #define rep(a, b) for(int a = 0; a < (b); ++a) 184 #define st first 185 #define nd second 186 #define pb push_back 187 #define all(a) a.begin(), a.end() 188 const int LIM=1e5+7; 189 ll T[LIM], P[LIM], n, k; 190 void solve() { 191 rep(i, n) T[i]=P[i]; 192 ll ans=0; 193 for(ll i=60; i>=0; --i) { 194 ll sum=0; 195 rep(j, n) { 196 if(T[j]&(1ll<<i)) continue; 197 ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i); 198 p+=ans^(p&ans); 199 sum+=p-T[j]; 200 if(sum > k){ 201 break; 202 } 203 } 204 if(sum>k) continue; 205 rep(j, n) { 206 if(T[j]&(1ll<<i)) continue; 207 ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i); 208 p+=ans^(p&ans); 209 T[j]=p; 210 } 211 ans+=1ll<<i; 212 k-=sum; 213 } 214 cout << ans << '\n'; 215 } 216 int main() { 217 ios_base::sync_with_stdio(0); cin.tie(0); 218 int q; 219 cin >> n >> q; 220 rep(i, n) cin >> P[i]; 221 while(q--) { 222 cin >> k; 223 solve(); 224 } 225 } 226 ``` 227 228 **Rate this problem** 229 230 Good 231 232 Mid 233 234 Bad 235 236 [1903D2 - Maximum And Queries (hard version)](/contest/1903/problem/D2 "Codeforces Round 912 (Div. 2)") 237 238 **Hint** 239 240 Try optimizing the greedy approach from $O$($n$) to $O$($1$). 241 242 **Solution** 243 244 Tutorial is loading... 245 246 **Code (C++)** 247 248 ``` 249 #include<bits/stdc++.h> 250 using namespace std; 251 typedef long double ld; 252 typedef long long ll; 253 #define rep(a, b) for(ll a = 0; a < (b); ++a) 254 #define st first 255 #define nd second 256 #define pb push_back 257 #define all(a) a.begin(), a.end() 258 const int LIM=1e6+7; 259 ll dpsum[1<<20][20], dpcnt[1<<20], T[LIM]; 260 int main() { 261 ios_base::sync_with_stdio(0); cin.tie(0); 262 ll n, q; 263 cin >> n >> q; 264 ll sto=0, sfrom=0; 265 rep(i, n) { 266 cin >> T[i]; 267 sto+=(1ll<<20ll)-T[i]; 268 sfrom+=T[i]; 269 ++dpcnt[T[i]]; 270 ll sum=0; 271 rep(j, 20) { 272 sum+=T[i]&(1ll<<j); 273 dpsum[T[i]][j]+=sum; 274 } 275 } 276 rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) dpcnt[j]+=dpcnt[j+(1<<i)]; 277 rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) rep(l, 20) dpsum[j][l]+=dpsum[j+(1<<i)][l]; 278 while(q--) { 279 ll k; 280 cin >> k; 281 if(k>=sto) { 282 k+=sfrom; 283 cout << k/n << '\n'; 284 continue; 285 } 286 ll ans=0; 287 for(ll i=19; i>=0; --i) { 288 ll x=(n-dpcnt[ans|(1<<i)])*(1ll<<i); 289 x-=dpsum[ans][i]-dpsum[ans|(1<<i)][i]; 290 if(x<=k) { 291 k-=x; 292 ans|=1<<i; 293 } 294 } 295 cout << ans << '\n'; 296 } 297 } 298 ``` 299 300 **Rate this problem** 301 302 Good 303 304 Mid 305 306 Bad 307 308 [1903E - Geo Game](/contest/1903/problem/E "Codeforces Round 912 (Div. 2)") 309 310 **Hint** 311 312 Do mod $2$ in all coordinates and see how many different types of points you have in the end. 313 314 **Solution** 315 316 Tutorial is loading... 317 318 **Code (C++)** 319 320 ``` 321 #include <bits/stdc++.h> 322 using namespace std; 323 int main(){ 324 int t; 325 cin>>t; 326 while(t--){ 327 int n; 328 cin>>n; 329 int sx,sy; 330 cin>>sx>>sy; 331 int x[n],y[n]; 332 set<int>p[2]; 333 for(int i = 0;i < n;i++){ 334 cin>>x[i]>>y[i]; 335 p[(x[i] % 2) ^ (y[i] % 2)].insert(i+1); 336 } 337 int v = (sx % 2) ^ (sy % 2); 338 if(p[v].size() >= p[v^1].size()){ 339 cout<<"First"<<endl; 340 v ^= 1; 341 for(int i = 0;i < n;i++){ 342 if(i % 2 == 0){ 343 int j; 344 if(!p[v].empty()){ 345 j = (*p[v].begin()); 346 p[v].erase(j); 347 } 348 else{ 349 j = (*p[v^1].begin()); 350 p[v^1].erase(j); 351 } 352 cout<<j<<endl; 353 } 354 else{ 355 int j; 356 cin>>j; 357 if(p[0].count(j)){ 358 p[0].erase(j); 359 } 360 else{ 361 p[1].erase(j); 362 } 363 } 364 } 365 } 366 else{ 367 cout<<"Second"<<endl; 368 for(int i = 0;i < n;i++){ 369 if(i % 2 == 1){ 370 int j; 371 if(!p[v].empty()){ 372 j = (*p[v].begin()); 373 p[v].erase(j); 374 } 375 else{ 376 j = (*p[v^1].begin()); 377 p[v^1].erase(j); 378 } 379 cout<<j<<endl; 380 } 381 else{ 382 int j; 383 cin>>j; 384 if(p[0].count(j)){ 385 p[0].erase(j); 386 } 387 else{ 388 p[1].erase(j); 389 } 390 } 391 } 392 } 393 } 394 } 395 ``` 396 397 **Rate this problem** 398 399 Good 400 401 Mid 402 403 Bad 404 405 [1903F - Babysitting](/contest/1903/problem/F "Codeforces Round 912 (Div. 2)") 406 407 **Hint** 408 409 Use binary search the answer and 2-sat. 410 411 **Solution** 412 413 Tutorial is loading... 414 415 **Code (C++)** 416 417 ``` 418 #include <bits/stdc++.h> 419 using namespace std; 420 typedef int ll; 421 const ll INF = 1e9+7; 422 const ll MOD = 998244353; 423 typedef pair<ll,ll> ii; 424 #define iii pair<ii,ll> 425 #define f(i,a,b) for(ll i = a;i < b;i++) 426 #define pb push_back 427 #define vll vector<ll> 428 #define F first 429 #define S second 430 #define all(x) (x).begin(), (x).end() 431 vector<vector<ll> >adj,rev; 432 vector<ll>order; 433 vector<ll>vis,comp; 434 ll c; 435 ll cur; 436 ll val(ll idx,bool v){ 437 return cur + (2 * idx + v); 438 } 439 void dfs1(ll idx){ 440 vis[idx] = true; 441 for(auto x:adj[idx]){ 442 if(!vis[x]){ 443 dfs1(x); 444 } 445 } 446 order.pb(idx); 447 } 448 void dfs2(ll idx){ 449 comp[idx] = c; 450 for(auto x:rev[idx]){ 451 if(!comp[x]){ 452 dfs2(x); 453 } 454 } 455 } 456 void build(ll s,ll e,ll idx){ 457 if(s == e){ 458 adj[idx].pb(val(s,0)); 459 rev[val(s,0)].pb(idx); 460 return; 461 } 462 ll mid = (s+e)/2; 463 build(s,mid,idx*2); 464 build(mid+1,e,idx*2+1); 465 adj[idx].pb(idx*2); 466 adj[idx].pb(idx*2+1); 467 rev[idx*2].pb(idx); 468 rev[idx*2+1].pb(idx); 469 } 470 void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){ 471 if(qs <= s && e <= qe){ 472 adj[val(k,1)].pb(idx); 473 rev[idx].pb(val(k,1)); 474 return; 475 } 476 if(s > qe || qs > e){ 477 return; 478 } 479 ll mid = (s+e)/2; 480 update(s,mid,qs,qe,idx*2,k); 481 update(mid+1,e,qs,qe,idx*2+1,k); 482 } 483 int main(void){ 484 ios_base::sync_with_stdio(0); 485 cin.tie(0); 486 ll t; 487 cin>>t; 488 while(t--){ 489 ll n,m; 490 cin>>n>>m; 491 ll u[m],v[m]; 492 f(i,0,m){ 493 cin>>u[i]>>v[i]; 494 } 495 ll l = 1,r = n; 496 ll ans = 1; 497 cur = 4*n; 498 while(l <= r){ 499 ll mid = (l+r)/2; 500 order.clear(); 501 vis.assign(6*n+5,0); 502 comp.assign(6*n+5,0); 503 adj.assign(6*n+5,vector<ll>()); 504 rev.assign(6*n+5,vector<ll>()); 505 f(i,0,m){ 506 adj[val(u[i],0)].pb(val(v[i],1)); 507 adj[val(v[i],0)].pb(val(u[i],1)); 508 rev[val(u[i],1)].pb(val(v[i],0)); 509 rev[val(v[i],1)].pb(val(u[i],0)); 510 } 511 build(1,n,1); 512 f(k,1,n+1){ 513 ll l = max(1,k - mid + 1),r = k-1; 514 update(1,n,l,r,1,k); 515 l = k+1; 516 r = min(n,k + mid - 1); 517 update(1,n,l,r,1,k); 518 } 519 bool ok = true; 520 c = 1; 521 f(i,1,n+1){ 522 if(!vis[val(i,0)]){ 523 dfs1(val(i,0)); 524 } 525 if(!vis[val(i,1)]){ 526 dfs1(val(i,1)); 527 } 528 } 529 reverse(order.begin(),order.end()); 530 for(auto x:order){ 531 if(!comp[x]){ 532 dfs2(x); 533 c++; 534 } 535 } 536 f(i,1,n+1){ 537 ok &= comp[val(i,0)] != comp[val(i,1)]; 538 } 539 if(ok){ 540 l = mid + 1; 541 ans = max(ans,mid); 542 } 543 else{ 544 r = mid - 1; 545 } 546 } 547 cout<<ans<<"\n"; 548 } 549 } 550 ``` 551 552 **jeroenodb's solution O(M log N)** 553 554 ``` 555 #pragma GCC optimize("O3") 556 #include "bits/stdc++.h" 557 using namespace std; 558 #define all(x) begin(x),end(x) 559 template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } 560 template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } 561 #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; 562 typedef long long ll; 563 typedef vector<int> vi; 564 typedef vector<basic_string<int>> vvi; 565 typedef pair<int,int> pi; 566 const int mxN = 1e5+1, oo = 1e9; 567 template<int (*merge)(int,int), int (*init)(int)> struct DSU{ 568 vi sz, dat; 569 DSU(int n) : sz(n,-1),dat(n) { 570 for(int i=0;i<n;++i) dat[i] = init(i); 571 } 572 void link(int a, int b) { 573 if(sz[a]>sz[b]) { 574 swap(a,b); 575 } 576 sz[a]+=sz[b]; 577 sz[b]=a; 578 dat[a] = merge(dat[a],dat[b]); 579 } 580 bool unite(int a, int b) { 581 int pa = find(a),pb = find(b); 582 if(pa!=pb) link(pa,pb); 583 return pa!=pb; 584 } 585 int get(int i) { 586 return dat[find(i)]; 587 } 588 int find(int a) { 589 if(sz[a]<0) return a; 590 return sz[a] = find(sz[a]); 591 } 592 }; 593 int dec(int i) {return i-1;} 594 int inc(int i) {return i+1;} 595 int mymin(int a, int b) {return min(a,b);} 596 int mymax(int a, int b) {return max(a,b);} 597 bool solve(const vvi& adj, const vvi& rev, int mid) { 598 int n = rev.size()/2; 599 600 DSU<mymin, dec> dsuL(n); 601 DSU<mymax, inc> dsuR(n); 602 auto getL = [&](int i) { 603 if(i>=n) i-=n; 604 int l = dsuL.get(i); 605 if(l==-1 or abs(i-l)>=mid) return 0; 606 return l+1; 607 }; 608 auto getR = [&](int i) { 609 if(i>=n) i-=n; 610 int r = dsuR.get(i); 611 if(r==n or abs(i-r)>=mid) return 0; 612 return r+1; 613 }; 614 auto rem = [&](int at) { 615 if(at>=n) at-=n; 616 if(at) dsuR.unite(at-1,at); 617 if(at+1<n) dsuL.unite(at,at+1); 618 }; 619 vector<bool> vis(n*2); 620 vi ord; 621 auto dfs = [&](auto&& self, int at) -> void { 622 vis[at]=1; 623 if(at<n) { 624 while(int l = getL(at)) self(self,l-1+n); 625 while(int r = getR(at)) self(self,r-1+n); 626 } else rem(at); 627 for(int to : adj[at]) if(!vis[to]) self(self,to); 628 ord.push_back(at); 629 630 }; 631 for(int i=0;i<2*n;++i) if(!vis[i]) dfs(dfs,i); 632 reverse(all(ord)); 633 634 fill(all(vis),0); 635 dsuL = DSU<mymin,dec>(n); 636 dsuR = DSU<mymax,inc>(n); 637 int comp=0; 638 vi comps(2*n); 639 auto dfs2 = [&](auto&& self, int at) -> void { 640 comps[at]=comp; 641 vis[at]=1; 642 if(at>=n) { 643 while(int l = getL(at)) self(self,l-1); 644 while(int r = getR(at)) self(self,r-1); 645 } else rem(at); 646 for(int to : rev[at]) if(!vis[to]) self(self,to); 647 648 }; 649 650 for(int i : ord) if(!vis[i]) { 651 dfs2(dfs2,i); 652 comp++; 653 } 654 for(int i=0;i<n;++i) if(comps[i]==comps[i+n]) return false; 655 return true; 656 657 } 658 void solve() { 659 int n,m; cin >> n >> m; 660 vvi adj(2*n),rev(2*n); 661 auto addE = [&](int u, int v) { 662 adj[u].push_back(v); 663 rev[v].push_back(u); 664 }; 665 for(int i=0;i<m;++i) { 666 int u,v; cin >> u >> v; 667 --u,--v; 668 addE(u+n,v); 669 addE(v+n,u); 670 } 671 672 int lo=1,hi=n; 673 while(lo<hi) { 674 int mid = (lo+hi+1)/2; 675 if(solve(adj,rev,mid)) { 676 lo= mid; 677 } else hi = mid-1; 678 } 679 cout << lo << '\n'; 680 } 681 682 int main() { 683 ios_base::sync_with_stdio(false); 684 cin.tie(NULL); 685 int t; cin >> t; 686 while(t--) solve(); 687 } 688 ``` 689 690 **Rate this problem** 691 692 Good 693 694 Mid 695 696 Bad