codeforces-scrape

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

1291.md (19734B)


      1 Source: https://codeforces.com/blog/entry/73563
      2 
      3 Hello everyone, this is the editorial for [Codeforces Round 616 (Div. 1)](/contest/1290 "Codeforces Round 616 (Div. 1)") and [Codeforces Round 616 (Div. 2)](/contest/1291 "Codeforces Round 616 (Div. 2)")! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b
      4 
      5 [1291A - Even But Not Even](/contest/1291/problem/A "Codeforces Round 616 (Div. 2)")
      6 
      7 Author: [265918](/profile/265918 "Candidate Master 265918")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21     ios::sync_with_stdio(false);
     22     cin.tie(nullptr);
     23     int t; cin >> t;
     24     while (t--) {
     25         int n; cin >> n;
     26         string s; cin >> s;
     27         int odd = 0;
     28         for (char c : s) if ((c - '0') & 1) odd++;
     29         if (odd <= 1) { cout << "-1\n"; continue; }
     30         int cnt = 0;
     31         for (char c : s) {
     32             if ((c - '0') & 1) { cout << c; cnt++; }
     33             if (cnt == 2) break;
     34         }
     35         cout << '\n';
     36     }
     37     return 0;
     38 }
     39 ```
     40 
     41 [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)")
     42 
     43 Author: [hugopm](/profile/hugopm "International Master hugopm")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Implementation**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 using namespace std;
     54 
     55 int main()
     56 {
     57     ios::sync_with_stdio(false); cin.tie(0);
     58 
     59     int nbTests; cin >> nbTests;
     60     while (nbTests--) {
     61 	    int nbElem; cin >> nbElem;
     62 	    vector<int> tab(nbElem);
     63 
     64 	    for (int i = 0; i < nbElem; ++i)
     65 		    cin >> tab[i];
     66 
     67 	    int prefixEnd = -1, suffixEnd = nbElem;
     68 
     69 	    for (int i = 0; i < nbElem; ++i) {
     70 		    if (tab[i] < i) break;
     71 		    prefixEnd = i;
     72 	    }
     73 	    for (int i = nbElem-1; i >= 0; --i) {
     74 		    if (tab[i] < (nbElem-1)-i) break;
     75 		    suffixEnd = i;
     76 	    }
     77 
     78 	    if (suffixEnd <= prefixEnd) // Non-empty intersection
     79 		    cout << "Yes\n";
     80 	    else
     81 		    cout << "No\n";
     82     }
     83 }
     84 ```
     85 
     86 [1290A - Mind Control](/contest/1290/problem/A "Codeforces Round 616 (Div. 1)")
     87 
     88 Author: [Ari](/profile/Ari "Master Ari")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Implementation (quadratic)**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 using namespace std;
     99 
    100 int main()
    101 {
    102     ios::sync_with_stdio(false); cin.tie(0);
    103 
    104     int nbTests; cin >> nbTests;
    105     while (nbTests--) {
    106 	    int nbElem, pos, nbControl;
    107 	    cin >> nbElem >> pos >> nbControl;
    108 
    109 	    int before = pos-1, behind = nbElem-pos;
    110 	    nbControl = min(nbControl, before);
    111 
    112 	    vector<int> tab(nbElem);
    113 	    for (int i = 0; i < nbElem; ++i) cin >> tab[i];
    114 
    115 	    int bestStrategy = 0;
    116 
    117 	    for (int orderFirst = 0; orderFirst <= nbControl; ++orderFirst) {
    118 		    int strategyAns = (int)(1e9) + 5;
    119 		    for (int opponentFirst = 0; opponentFirst <= before-nbControl; ++opponentFirst) {
    120 			    int caseAns = max(tab[orderFirst + opponentFirst], tab[orderFirst + opponentFirst + behind]); 
    121 			    strategyAns = min(strategyAns, caseAns);
    122 		    }
    123 		    bestStrategy = max(bestStrategy, strategyAns);
    124 	    }
    125 
    126 	    cout << bestStrategy << "\n";
    127     }
    128 }
    129 ```
    130 
    131 **Implementation (linear)**
    132 
    133 ```
    134 #include <bits/stdc++.h>
    135 using namespace std;
    136 
    137 void solve() {
    138     int n, m, k;
    139     cin >> n >> m >> k;
    140     k = min(k, m - 1);
    141     vector<int> a(n);
    142     for(auto &x : a)
    143         cin >> x;
    144     vector<int> b;
    145     for(int i = 0; i < m; i++)
    146         b.push_back(max(a[i], a[i + n - m]));
    147     int sz = m - k;
    148     int ans = 0;
    149     deque<int> q;
    150     for(int i = 0, j = 0; i + sz - 1 < m; i++) {
    151         while(q.size() && q.front() < i)
    152             q.pop_front();
    153         while(j < i + sz) {
    154             while(q.size() && b[q.back()] >= b[j])
    155                 q.pop_back();
    156             q.push_back(j++);
    157         }
    158         ans = max(ans, b[q.front()]);
    159     }
    160     cout << ans << '\n';
    161 }
    162 
    163 int main() {
    164     int t;
    165     cin >> t;
    166     while(t--)
    167         solve();
    168 }
    169 ```
    170 
    171 [1290B - Irreducible Anagrams](/contest/1290/problem/B "Codeforces Round 616 (Div. 1)")
    172 
    173 Author: [Ari](/profile/Ari "Master Ari")
    174 
    175 **Tutorial**
    176 
    177 Tutorial is loading...
    178 
    179 **Implementation**
    180 
    181 ```
    182 #include <bits/stdc++.h>
    183 using namespace std;
    184 
    185 const int N = 200005;
    186 
    187 char s[N];
    188 int n, q, l, r, sum[N][26];
    189 
    190 int main() {
    191     ios_base::sync_with_stdio(false);
    192     cin.tie(nullptr);
    193     cin >> (s + 1);
    194     n = strlen(s + 1);
    195     for (int i = 1; i <= n; i++) {
    196         for (int j = 0; j < 26; j++) {
    197             sum[i][j] = sum[i - 1][j];
    198         }
    199         sum[i][s[i] - 'a']++;
    200     }
    201     cin >> q;
    202     while (q--) {
    203         cin >> l >> r;
    204         int cnt = 0;
    205         for (int i = 0; i < 26; i++) {
    206             cnt += (sum[r][i] - sum[l - 1][i] > 0);
    207         }
    208         if (l == r || cnt >= 3 || s[l] != s[r]) {
    209             cout << "Yes\n";
    210         } else {
    211             cout << "No\n";
    212         }
    213     }
    214 }
    215 ```
    216 
    217 [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)")
    218 
    219 Author: [hugopm](/profile/hugopm "International Master hugopm")
    220 
    221 **Tutorial**
    222 
    223 Tutorial is loading...
    224 
    225 **Implementation (preprocess with DFS)**
    226 
    227 ```
    228 #include <bits/stdc++.h>
    229 using namespace std;
    230 using pii = pair<int, int>;
    231 
    232 const int lim = 1000*1000 + 5;
    233 int nbElem, nbSub;
    234 vector<int> subset[lim];
    235 int side[lim];
    236 int isIn[lim][2];
    237 string ini;
    238 int rep = 0;
    239 
    240 int drepr[lim]; 
    241 int dsz[lim];
    242 int cnt[lim][2];
    243 
    244 int dfind(int x)
    245 {
    246     if (drepr[x] != x) drepr[x] = dfind(drepr[x]);
    247     return drepr[x];
    248 }
    249 
    250 void add(int cc, int s0, int s1)
    251 {
    252     cc = dfind(cc);
    253     rep -= min(cnt[cc][0], cnt[cc][1]);
    254     cnt[cc][0] = min(lim, cnt[cc][0] + s0);
    255     cnt[cc][1] = min(lim, cnt[cc][1] + s1);
    256     rep += min(cnt[cc][0], cnt[cc][1]);
    257 }
    258 
    259 void dmerge(int a, int b)
    260 {
    261     a = dfind(a); b = dfind(b);
    262     if (a == b) return;
    263     if (dsz[a] < dsz[b]) swap(a,b);
    264     add(a, cnt[b][0], cnt[b][1]);
    265     add(b, -cnt[b][0], -cnt[b][1]);
    266     dsz[a] += dsz[b];
    267     drepr[b] = a;
    268 }
    269 
    270 void dfs(int nod)
    271 {
    272     cnt[nod][side[nod]] = 1;
    273     for (int elem : subset[nod]) {
    274 	    if (isIn[elem][1] == -1) continue;
    275 	    int oth = isIn[elem][0] + isIn[elem][1] - nod;
    276 	    if (side[oth] == -1) {
    277 		    side[oth] = side[nod] ^ (ini[elem] == '0');
    278 		    dfs(oth);
    279 	    }
    280     }
    281 }
    282 
    283 int main()
    284 {
    285     ios::sync_with_stdio(false);
    286     cin.tie(0);
    287     cin >> nbElem >> nbSub;
    288     cin >> ini;
    289     fill(side,side+lim,-1);
    290     iota(drepr,drepr+lim,0);
    291     fill_n(&isIn[0][0], 2*lim, -1);
    292 
    293     for (int sub = 0; sub < nbSub; ++sub) {
    294 	    int st; cin >> st;
    295 	    subset[sub].resize(st);
    296 	    for (int pos = 0; pos < st; ++pos) {
    297 		    int elem; cin >> elem; --elem;
    298 		    subset[sub][pos] = elem;
    299 		    if (isIn[elem][0] == -1) isIn[elem][0] = sub;
    300 		    else isIn[elem][1] = sub;
    301 	    }
    302     }
    303 
    304     for (int sub = 0; sub < nbSub; ++sub) {
    305 	    if (side[sub] == -1) {
    306 		    side[sub] = 0;
    307 		    dfs(sub);
    308 	    }
    309     }
    310 
    311     for (int elem = 0; elem < nbElem; ++elem) {
    312 	    int n0 = isIn[elem][0], n1 = isIn[elem][1];
    313 	    if (n0 != -1 && n1 == -1) {
    314 		    int destroy = side[n0] ^ (ini[elem] == '0');
    315 		    if (destroy == 1) add(n0, 0, lim);
    316 		    else add(n0, lim, 0);	
    317 	    } else if (n0 != -1) {
    318 		    dmerge(n0, n1);
    319 	    }
    320 	    cout << rep << "\n";
    321     }
    322 }
    323 ```
    324 
    325 **Implementation (dynamic bipartite DSU)**
    326 
    327 ```
    328 #include <bits/stdc++.h>
    329 #define fi first
    330 #define se second
    331 using namespace std;
    332 
    333 const int N = 1E6 + 5, K = 1E6 + 5, INF = 1E9 + 7;
    334 
    335 int n, k, c, v, ans = 0, dsu[K];
    336 char s[N];
    337 vector<int> adj[N];
    338 
    339 struct node {
    340     int l, r, xo;
    341 
    342     node(int _l = 0, int _r = 0, int _xo = 0) : l(_l), r(_r), xo(_xo) {}
    343 
    344     int get() {
    345         return min(l, r);
    346     }
    347 
    348     inline void operator+=(node oth) {
    349         l = min(INF, l + oth.l);
    350         r = min(INF, r + oth.r);
    351     }
    352 } val[K];
    353 
    354 pair<int, int> trace(int u) {
    355     if (dsu[u] < 0) {
    356         return {u, 0};
    357     } else {
    358         pair<int, int> tmp = trace(dsu[u]);
    359         dsu[u] = tmp.fi;
    360         val[u].xo ^= tmp.se;
    361         return {dsu[u], val[u].xo};
    362     }
    363 }
    364 
    365 int main() {
    366     ios_base::sync_with_stdio(false);
    367     cin.tie(nullptr);
    368     cin >> n >> k >> (s + 1);
    369     for (int i = 1; i <= k; i++) {
    370         dsu[i] = -1;
    371         val[i] = node(1, 0, 0);
    372         cin >> c;
    373         while (c--) {
    374             cin >> v;
    375             adj[v].push_back(i);
    376         }
    377     }
    378     for (int i = 1; i <= n; i++) {
    379         int typ = (s[i] - '0') ^ 1;
    380         if (ans != -1) {
    381             if (adj[i].size() == 1) {
    382                 pair<int, int> u = trace(adj[i][0]);
    383                 ans -= val[u.fi].get();
    384                 val[u.fi] += node((u.se == typ) * INF, (u.se != typ) * INF);
    385                 ans += val[u.fi].get();
    386             } else if (adj[i].size() == 2) {
    387                 pair<int, int> u = trace(adj[i][0]);
    388                 pair<int, int> v = trace(adj[i][1]);
    389                 if (u.fi != v.fi) {
    390                     ans -= val[u.fi].get() + val[v.fi].get();
    391                     if (dsu[u.fi] > dsu[v.fi]) {
    392                         swap(u, v);
    393                     }
    394                     if (u.se ^ v.se ^ typ) {
    395                         swap(val[v.fi].l, val[v.fi].r);
    396                         val[v.fi].xo = 1;
    397                     }
    398                     dsu[u.fi] += dsu[v.fi];
    399                     dsu[v.fi] = u.fi;
    400                     val[u.fi] += val[v.fi];
    401                     ans += val[u.fi].get();
    402                 }
    403             }
    404         }
    405         cout << ans << '\n';
    406     }
    407 }
    408 ```
    409 
    410 [1290D - Coffee Varieties (hard version)](/contest/1290/problem/D "Codeforces Round 616 (Div. 1)")
    411 
    412 Author: [hugopm](/profile/hugopm "International Master hugopm")
    413 
    414 **Tutorial**
    415 
    416 Tutorial is loading...
    417 
    418 **Implementation**
    419 
    420 ```
    421 #include <bits/stdc++.h>
    422 using namespace std;
    423 
    424 bool ask(int pos)
    425 {
    426     cout << "? " << pos+1 << endl << flush;
    427     char c; cin >> c;
    428     if (c == 'E') exit(0);
    429     return (c == 'Y');
    430 }
    431 
    432 int main()
    433 {
    434     int nbElem, memSize, nbBlocks;
    435     cin >> nbElem >> memSize;
    436     nbBlocks = nbElem / memSize;
    437 
    438     vector<bool> isAlive(nbElem, true);
    439 
    440     for (int startBlock = 0; startBlock < nbBlocks; ++startBlock) {
    441 	    int delta = 0;
    442 	    cout << "R" << endl << flush;
    443 	    for (int iDo = 0; iDo < nbBlocks; ++iDo) {
    444 		    int curBlock = (startBlock+delta+nbBlocks) % nbBlocks;
    445 		    int st = curBlock*memSize;
    446 		    for (int elem = st; elem < st+memSize; ++elem) {
    447 			    if (isAlive[elem]) {
    448 				    if (ask(elem)) isAlive[elem] = false;
    449 			    }
    450 		    }
    451 
    452 		    if (delta >= 0) ++delta;
    453 		    delta = -delta;
    454 	    }
    455     }
    456 
    457     int nbAlive = count(isAlive.begin(), isAlive.end(), true);
    458     cout << "! " << nbAlive << endl << flush;
    459 }
    460 ```
    461 
    462 [1290E - Cartesian Tree](/contest/1290/problem/E "Codeforces Round 616 (Div. 1)")
    463 
    464 Author: [gamegame](/profile/gamegame "International Grandmaster gamegame")
    465 
    466 **Tutorial**
    467 
    468 Tutorial is loading...
    469 
    470 **Implementation**
    471 
    472 ```
    473 #include<bits/stdc++.h>
    474 using namespace std;
    475 typedef long long ll;
    476 const int N=3e5+1;
    477 const int ts=1<<21;
    478 int n;
    479 ll mx[ts],se[ts],mxc[ts];//max, 2nd max, max count
    480 int sz;
    481 ll ch[N];//which values are changed
    482 ll df[N];//change in frequency
    483 void pass(int id,int c){
    484     if(mx[c]>mx[id]) mx[c]=mx[id];
    485 }
    486 void push(int id){
    487     pass(id,id*2);
    488     pass(id,id*2+1);
    489 }
    490 void pull(int id){
    491     mx[id]=max(mx[id*2],mx[id*2+1]);
    492     mxc[id]=0;
    493     if(mx[id]==mx[id*2]) mxc[id]+=mxc[id*2];
    494     if(mx[id]==mx[id*2+1]) mxc[id]+=mxc[id*2+1];
    495     se[id]=max(se[id*2],se[id*2+1]);
    496     if(mx[id*2]!=mx[id]) se[id]=max(se[id],mx[id*2]);
    497     if(mx[id*2+1]!=mx[id]) se[id]=max(se[id],mx[id*2+1]);
    498 }
    499 void upd(int id,int l,int r,int ql,int qr,int v){
    500     if(l>qr || r<ql || mx[id]<=v) return;
    501     if(ql<=l && r<=qr && se[id]<v){
    502 	    ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
    503 	    mx[id]=v;
    504 	    ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
    505 	    return;
    506     }
    507     push(id);
    508     int mid=(l+r)/2;
    509     upd(id*2,l,mid,ql,qr,v);
    510     upd(id*2+1,mid+1,r,ql,qr,v);
    511     pull(id);
    512 }
    513 void upd2(int id,int l,int r,int p,int v){
    514     if(l==r){
    515 	    ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
    516 	    mx[id]=v;
    517 	    ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
    518 	    return;
    519     }
    520     push(id);
    521     int mid=(l+r)/2;
    522     if(p<=mid) upd2(id*2,l,mid,p,v);
    523     else upd2(id*2+1,mid+1,r,p,v);
    524     pull(id);
    525 }
    526 void build(int id,int l,int r){
    527     mx[id]=0;mxc[id]=r-l+1;se[id]=-1e9;
    528     if(l==r) return;
    529     int mid=(l+r)/2;
    530     build(id*2,l,mid);
    531     build(id*2+1,mid+1,r);
    532 }
    533 /////////////////////////////////////////////////
    534 ll bit1[N],bit2[N];
    535 void bupd1(int id,ll v){
    536     for(int i=id; i<=n ;i+=i&-i) bit1[i]+=v;
    537 }
    538 void bupd2(int id,ll v){
    539     for(int i=id; i<=n ;i+=i&-i) bit2[i]+=v;
    540 }
    541 ll bqry1(int id){
    542     ll res=0;
    543     for(int i=id; i>=1 ;i-=i&-i) res+=bit1[i];
    544     return res;
    545 }
    546 ll bqry2(int id){
    547     ll res=0;
    548     for(int i=id; i>=1 ;i-=i&-i) res+=bit2[i];
    549     return res;
    550 }
    551 int a[N],p[N];
    552 ll ans[N];
    553 set<int>s,t;
    554 void magic(int mg){
    555     s.clear();t.clear();build(1,1,n);
    556     for(int i=1; i<=n ;i++) bit1[i]=bit2[i]=0;
    557     s.insert(p[1]);//set of existed elements
    558     t.insert(p[1]);//set of l that maxr[] is not null
    559     bupd1(p[1],1);
    560     int mx=p[1];//largest existed position
    561     upd2(1,1,n,p[1],p[1]);
    562     bupd2(p[1],-1);
    563     ll tot=-1;
    564     for(int i=2; i<=n ;i++){
    565 	    int cur=p[i];
    566 	    auto it=s.lower_bound(cur);
    567 	    bool rm=(it==s.end());//new element is rightmost
    568 	    int nxt=0;
    569 	    if(!rm) nxt=*it;//next
    570 	    if(it==s.begin()){//new element is leftmost
    571 		    tot-=bqry1(cur);bupd2(cur,-1);
    572 		    t.insert(cur);
    573 		    upd2(1,1,n,cur,mx);
    574 	    }
    575 	    else{
    576 		    int prv=*(--it);
    577 		    upd(1,1,n,1,prv,prv);
    578 		    if(rm) mx=cur;
    579 		    else{
    580 			    upd2(1,1,n,nxt,mx);
    581 			    if(t.find(nxt)==t.end()){
    582 				    tot-=bqry1(nxt);bupd2(nxt,-1);
    583 				    t.insert(nxt);
    584 			    }
    585 		    }
    586 		    upd2(1,1,n,*s.begin(),mx);
    587 	    }
    588 	    s.insert(cur);
    589 	    tot+=bqry2(n)-bqry2(cur-1);
    590 	    bupd1(cur,1);
    591 	    for(int j=1; j<=sz ;j++){
    592 		    if(ch[j]!=0 && df[ch[j]]!=0){
    593 			    tot+=df[ch[j]]*bqry1(ch[j]);
    594 			    bupd2(ch[j],df[ch[j]]);
    595 			    df[ch[j]]=0;
    596 		    }
    597 	    }
    598 	    sz=0;
    599 	    ans[i]+=tot;
    600     }
    601 }
    602 void solve(){
    603     for(int i=1; i<=n ;i++){
    604 	    p[a[i]]=i;ans[i]=0;
    605     }
    606     magic(1);
    607     for(int i=1; i<=n ;i++) p[i]=n+1-p[i];
    608     magic(0);
    609     for(int i=1; i<=n ;i++) ans[i]+=1;
    610     for(int i=1; i<=n ;i++) cout << ans[i] << '\n';
    611 }
    612 int main(){
    613     ios::sync_with_stdio(false);
    614     cin >> n;
    615     for(int i=1; i<=n ;i++) cin >> a[i];
    616     solve();
    617 }
    618 ```
    619 
    620 [1290F - Making Shapes](/contest/1290/problem/F "Codeforces Round 616 (Div. 1)")
    621 
    622 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")
    623 
    624 **Tutorial**
    625 
    626 Tutorial is loading...
    627 
    628 **Implementation**
    629 
    630 ```
    631 #include <bits/stdc++.h>
    632 using namespace std;
    633 
    634 const int N = 5, MX = 4 * N, LG = 31, MOD = 998244353;
    635 
    636 int n, m, x[N], y[N];
    637 int px[1 << N], nx[1 << N], py[1 << N], ny[1 << N];
    638 int dp[LG][MX][MX][MX][MX][2][2];
    639 
    640 void add(int &x, int y) {
    641     x += y;
    642     if (x >= MOD) {
    643         x -= MOD;
    644     }
    645 }
    646 
    647 int main() {
    648     ios_base::sync_with_stdio(false);
    649     cin.tie(nullptr);
    650     cin >> n >> m;
    651     for (int i = 0; i < n; i++) {
    652         cin >> x[i] >> y[i];
    653     }
    654     for (int msk = 0; msk < (1 << n); msk++) {
    655         for (int i = 0; i < n; i++) {
    656             if (msk >> i & 1) {
    657                 (x[i] < 0 ? nx : px)[msk] += abs(x[i]);
    658                 (y[i] < 0 ? ny : py)[msk] += abs(y[i]);
    659             }
    660         }
    661     }
    662     int mpx = max(1, px[(1 << n) - 1]);
    663     int mpy = max(1, py[(1 << n) - 1]);
    664     int mnx = max(1, nx[(1 << n) - 1]);
    665     int mny = max(1, ny[(1 << n) - 1]);
    666     dp[0][0][0][0][0][0][0] = 1;
    667     for (int lg = 0; (1 << lg) <= m; lg++) {                                // bit position
    668         for (int cpx = 0; cpx < mpx; cpx++) {                               // carry of positive x
    669             for (int cpy = 0; cpy < mpy; cpy++) {                           // carry of positive y
    670                 for (int cnx = 0; cnx < mnx; cnx++) {                       // carry of negative x
    671                     for (int cny = 0; cny < mny; cny++) {                   // carry of negative y
    672                         for (int sx = 0; sx < 2; sx++) {                    // is the suffix of x greater than the suffix of m
    673                             for (int sy = 0; sy < 2; sy++) {                // is the suffix of y greater than the suffix of m
    674                                 for (int msk = 0; msk < (1 << n); msk++) {  // iterating over the mask of the current bit position
    675                                     int spx = cpx + px[msk];
    676                                     int spy = cpy + py[msk];
    677                                     int snx = cnx + nx[msk];
    678                                     int sny = cny + ny[msk];
    679                                     if (((spx ^ snx) & 1) || ((spy ^ sny) & 1)) {
    680                                         continue;
    681                                     }
    682                                     int bx = spx & 1, by = spy & 1;
    683                                     int nsx = (bx < (m >> lg & 1) ? 0 : bx > (m >> lg & 1) ? 1 : sx);
    684                                     int nsy = (by < (m >> lg & 1) ? 0 : by > (m >> lg & 1) ? 1 : sy);
    685                                     add(dp[lg + 1][spx / 2][spy / 2][snx / 2][sny / 2][nsx][nsy], dp[lg][cpx][cpy][cnx][cny][sx][sy]);
    686                                 }
    687                             }
    688                         }
    689                     }
    690                 }
    691             }
    692         }
    693     }
    694     cout << (dp[__lg(m) + 1][0][0][0][0][0][0] + MOD - 1) % MOD << '\n';
    695 }
    696 ```
    697 
    698 #### Theme and easter eggs
    699 
    700 **Spoilers**
    701 
    702 Oh boi this is gonna be interesting ( ͡° ͜ʖ ͡°)
    703 
    704 The theme of the contest can be found by concatenating the first letter of each paragraph of the announcement ( ͡° ͜ʖ ͡°) From now on, we will refer to six-digit codes found in each problem statement as "sauce". ( ͡° ͜ʖ ͡°)
    705 
    706 For [1291A - Even But Not Even](/contest/1291/problem/A "Codeforces Round 616 (Div. 2)"), the obvious sauces are $177013$ and $265918$. Along with this, break down the really long number in the sample input, you will get 4 sauces: $222373$, $204424$, $185217$, and $171912$.
    707 
    708 For [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)"), the sauces are $282865$, $256988$ (found as inline examples for non-sharpened arrays), and $248618$ (found in the sample input).
    709 
    710 For [1290A - Mind Control](/contest/1290/problem/A "Codeforces Round 616 (Div. 1)"), the sauces are $292385$ and $213604$ (found in the sample input).
    711 
    712 For [1290B - Irreducible Anagrams](/contest/1290/problem/B "Codeforces Round 616 (Div. 1)"), look at the second sample input. There are 6 queries, concatenate $l$ and $r$ of all queries to get $122153$ and $242975$.
    713 
    714 For [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)"), the binary string of the last sample input encodes a sauce into binary. Decode it into decimal to get $299782$. Fun side note, while developing this problem, the intended sauce was $299742$, but I typed in the wrong code to the binary converter. It turned out to be better btw. ( ͡° ͜ʖ ͡°)
    715 
    716 For [1290D - Coffee Varieties (hard version)](/contest/1290/problem/D "Codeforces Round 616 (Div. 1)"), the ? queries of the second sample output gives you $264525$. Additionally, the ! query gives you page $6$ of the sauce. ( ͡° ͜ʖ ͡°)
    717 
    718 For [1290E - Cartesian Tree](/contest/1290/problem/E "Codeforces Round 616 (Div. 1)") , the permutation of the second sample input gives you $124563$.
    719 
    720 For [1290F - Making Shapes](/contest/1290/problem/F "Codeforces Round 616 (Div. 1)"), the third sample output gives you the sauce $296161$.
    721 
    722 **UPD**: As I write these lines, $300000$ has been born. So unironically, the constraints of [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)") and [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)") are now sauces. ( ͡° ͜ʖ ͡°)
    723 
    724 Hope you have fun with the easter eggs we provided. ( ͡~ ͜ʖ ͡°)