codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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