codeforces-scrape

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

1980.md (12394B)


      1 Source: https://codeforces.com/blog/entry/130135
      2 
      3 [1980A - Problem Generator](/contest/1980/problem/A "Codeforces Round 950 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n, m = map(int, input().split())
     16     a = input()
     17     ans = 0
     18     for ch in range(ord('A'), ord('H')):
     19         ans += max(0, m - a.count(chr(ch)))
     20     print(ans)
     21     
     22     
     23 for _ in range(int(input())):
     24     solve()
     25 ```
     26 
     27 [1980B - Choosing Cubes](/contest/1980/problem/B "Codeforces Round 950 (Div. 3)")
     28 
     29 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution**
     36 
     37 ```
     38 def solve():
     39     n, f, k = map(int, input().split())
     40     f -= 1
     41     k -= 1
     42     a = list(map(int, input().split()))
     43     x = a[f]
     44     a.sort(reverse=True)
     45     if a[k] > x:
     46         print("NO")
     47     elif a[k] < x:
     48         print("YES")
     49     else:
     50         print("YES" if k == n - 1 or a[k + 1] < x else "MAYBE")
     51  
     52 t = int(input())
     53 for _ in range(t):
     54     solve()
     55 ```
     56 
     57 [1980C - Sofia and the Lost Operations](/contest/1980/problem/C "Codeforces Round 950 (Div. 3)")
     58 
     59 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40")
     60 
     61 **Tutorial**
     62 
     63 Tutorial is loading...
     64 
     65 **Solution**
     66 
     67 ```
     68 #include <stdio.h>
     69 #include <stdbool.h>
     70  
     71 #define MAXN 200200
     72 #define MAXM 200200
     73  
     74 int n, m, k;
     75 int arr[MAXN], brr[MAXN], drr[MAXM], buf[MAXN];
     76  
     77 int cmp_i32(const void* pa, const void* pb) {
     78     return *(const int*)pa - *(const int*)pb;
     79 }
     80  
     81 void build() {
     82     k = 0;
     83     for (int i = 0; i < n; ++i) {
     84         if (arr[i] != brr[i])
     85             buf[k++] = brr[i];
     86     }
     87     qsort(buf, k, sizeof(*buf), cmp_i32);
     88 }
     89  
     90 bool check() {
     91     for (int i = 0; i < n; ++i)
     92         if (brr[i] == drr[m - 1])
     93             return true;
     94     return false;
     95 }
     96  
     97 bool solve() {
     98     if (!check()) return false;
     99     qsort(drr, m, sizeof(*drr), cmp_i32);
    100     int ib = 0, id = 0;
    101     while (ib < k && id < m) {
    102         if (buf[ib] == drr[id])
    103             ++ib, ++id;
    104         else if (buf[ib] < drr[id])
    105             return false;
    106         else ++id;
    107     }
    108     return ib == k;
    109 }
    110  
    111 int main() {
    112     int t; scanf("%d", &t);
    113     while (t--) {
    114         scanf("%d", &n);
    115         for (int i = 0; i < n; ++i)
    116             scanf("%d", arr + i);
    117         for (int i = 0; i < n; ++i)
    118             scanf("%d", brr + i);
    119         scanf("%d", &m);
    120         for (int j = 0; j < m; ++j)
    121             scanf("%d", drr + j);
    122         build();
    123         if (solve()) printf("YES\n");
    124         else printf("NO\n");
    125     }
    126 }
    127 ```
    128 
    129 [1980D - GCD-sequence](/contest/1980/problem/D "Codeforces Round 950 (Div. 3)")
    130 
    131 Idea: [myav](/profile/myav "Pupil myav") Prepared by: [myav](/profile/myav "Pupil myav")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Solution**
    138 
    139 ```
    140 #include <bits/stdc++.h>
    141 using namespace std;
    142  
    143 bool good(vector<int>&b){
    144     int g = __gcd(b[0], b[1]);
    145     for(int i = 1; i < int(b.size()) - 1; i++){
    146         int cur_gcd = __gcd(b[i], b[i + 1]);
    147         if(g > cur_gcd) return false;
    148         g = cur_gcd;
    149     }
    150     return true;
    151 }
    152  
    153 bool solve(){
    154     int n;
    155     cin >> n;
    156     vector<int>a(n);
    157     for(int i = 0; i < n; i++){
    158         cin >> a[i];
    159     }
    160  
    161     int g = -1;
    162     int to_del = -1;
    163     for(int i = 0; i < n - 1; i++){
    164         int cur_gcd = __gcd(a[i], a[i + 1]);
    165         if(cur_gcd < g){
    166             to_del = i;
    167             break;
    168         }
    169         g = cur_gcd;
    170     }
    171     if(to_del == -1) return true;
    172     vector<int>b0 = a, b1 = a, b2 = a;
    173     if(to_del > 0) b0.erase(b0.begin() + to_del - 1);
    174     b1.erase(b1.begin() + to_del);
    175     if(to_del < n - 1) b2.erase(b2.begin() + to_del + 1);
    176     return good(b0) || good(b1) || good(b2);
    177 }
    178  
    179 int main(){
    180     int t;
    181     cin >> t;
    182     while(t--){
    183         cout << (solve() ? "YES" : "NO") << "\n";
    184     }
    185 }
    186 ```
    187 
    188 [1980E - Permutation of Rows and Columns](/contest/1980/problem/E "Codeforces Round 950 (Div. 3)")
    189 
    190 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    191 
    192 **Tutorial**
    193 
    194 Tutorial is loading...
    195 
    196 **Solution**
    197 
    198 ```
    199 #include <iostream>
    200 #include <vector>
    201 #include <algorithm>
    202 #include <set>
    203  
    204 using namespace std;
    205  
    206 typedef long long ll;
    207 typedef vector<int> vi;
    208 typedef vector<vi> vvi;
    209  
    210 vi read_ints(int n) {
    211     vi res(n);
    212     for (int i = 0; i < n; ++i) {
    213         cin >> res[i];
    214     }
    215     return res;
    216 }
    217  
    218 vvi read_matrix(int n, int m) {
    219     vvi res(n);
    220     for (int i = 0; i < n; ++i) {
    221         res[i] = read_ints(m);
    222     }
    223     return res;
    224 }
    225  
    226 void solve() {
    227     int n, m;
    228     cin >> n >> m;
    229     vvi a = read_matrix(n, m), b = read_matrix(n, m);
    230     int nm = n * m;
    231     vi pos1i(nm), pos2i(nm), pos1j(nm), pos2j(nm);
    232     for (int i = 0; i < n; ++i) {
    233         for (int j = 0; j < m; ++j) {
    234             int x = a[i][j] - 1;
    235             int y = b[i][j] - 1;
    236             pos1i[x] = pos2i[y] = i;
    237             pos1j[x] = pos2j[y] = j;
    238         }
    239     }
    240     vector<set<int>> pi(nm), pj(nm);
    241     for (int x = 0; x < nm; ++x) {
    242         int i1 = pos1i[x], i2 = pos2i[x];
    243         int j1 = pos1j[x], j2 = pos2j[x];
    244         pi[i1].insert(i2);
    245         pj[j1].insert(j2);
    246     }
    247     for (int x = 0; x < nm; ++x) {
    248         if (pi[x].size() > 1 || pj[x].size() > 1) {
    249             cout << "NO\n";
    250             return;
    251         }
    252     }
    253     cout << "YES\n";
    254 }
    255  
    256 int main() {
    257     int t;
    258     cin >> t;
    259     for (int _ = 0; _ < t; ++_) {
    260         solve();
    261     }
    262     return 0;
    263 }
    264 ```
    265 
    266 [1980F1 - Field Division (easy version)](/contest/1980/problem/F1 "Codeforces Round 950 (Div. 3)")
    267 
    268 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    269 
    270 **Tutorial**
    271 
    272 Tutorial is loading...
    273 
    274 **Solution**
    275 
    276 ```
    277 #include <bits/stdc++.h>
    278  
    279 #define int long long
    280 #define pb emplace_back
    281 #define mp make_pair
    282 #define x first
    283 #define y second
    284 #define all(a) a.begin(), a.end()
    285 #define rall(a) a.rbegin(), a.rend()
    286  
    287 typedef long double ld;
    288 typedef long long ll;
    289  
    290 using namespace std;
    291  
    292 mt19937 rnd(time(nullptr));
    293  
    294 const ll inf = 1e9 + 1;
    295 const ll M = 998244353;
    296 const ld pi = atan2(0, -1);
    297 const ld eps = 1e-6;
    298  
    299 bool cmp(pair<int, int> &a, pair<int, int> &b){
    300     if(a.x != b.x) return a.x > b.x;
    301     return a.y < b.y;
    302 }
    303  
    304 void solve(int tc){
    305     int n, m, k;
    306     cin >> n >> m >> k;
    307     vector<pair<int, int>> a(k);
    308     map<pair<int, int>, int> idx;
    309     for(int i = 0; i < k; ++i){
    310         cin >> a[i].x >> a[i].y;
    311         idx[a[i]] = i;
    312     }
    313     sort(all(a), cmp);
    314     vector<int> ans(k);
    315     int total = 0;
    316     int cur = m + 1;
    317     int last = n;
    318     for(auto e: a){
    319         if(cur > e.y) {
    320             ans[idx[e]] = 1;
    321             total += (cur - 1) * (last - e.x);
    322             cur = e.y;
    323             last = e.x;
    324         }
    325     }
    326     total += (cur - 1) * last;
    327     cout << total << "\n";
    328     for(int e: ans) cout << e << " ";
    329 }
    330  
    331 bool multi = true;
    332  
    333 signed main() {
    334     int t = 1;
    335     if (multi)cin >> t;
    336     for (int i = 1; i <= t; ++i) {
    337         solve(i);
    338         cout << "\n";
    339     }
    340     return 0;
    341 }
    342 ```
    343 
    344 [1980F2 - Field Division (hard version)](/contest/1980/problem/F2 "Codeforces Round 950 (Div. 3)")
    345 
    346 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    347 
    348 **Tutorial**
    349 
    350 Tutorial is loading...
    351 
    352 **Solution**
    353 
    354 ```
    355 #include <bits/stdc++.h>
    356  
    357 #define int long long
    358 #define pb emplace_back
    359 #define mp make_pair
    360 #define x first
    361 #define y second
    362 #define all(a) a.begin(), a.end()
    363 #define rall(a) a.rbegin(), a.rend()
    364  
    365 typedef long double ld;
    366 typedef long long ll;
    367  
    368 using namespace std;
    369  
    370 mt19937 rnd(time(nullptr));
    371  
    372 const ll inf = 1e9 + 1;
    373 const ll M = 998244353;
    374 const ld pi = atan2(0, -1);
    375 const ld eps = 1e-6;
    376  
    377 bool cmp(pair<int, int> &a, pair<int, int> &b){
    378     if(a.x != b.x) return a.x > b.x;
    379     return a.y < b.y;
    380 }
    381  
    382 void solve(int tc){
    383     int n, m, k;
    384     cin >> n >> m >> k;
    385     vector<pair<int, int>> a(k);
    386     map<pair<int, int>, int> idx;
    387     for(int i = 0; i < k; ++i){
    388         cin >> a[i].x >> a[i].y;
    389         idx[a[i]] = i;
    390     }
    391     idx[{0, 0}] = k++;
    392     a.emplace_back(0, 0);
    393     sort(all(a), cmp);
    394     vector<int> ans(k);
    395     vector<int> total(k + 1), cur(k + 1, m + 1), last(k + 1, n);
    396     for(int i = 1; i <= k; ++i){
    397         auto e = a[i - 1];
    398         total[i] = total[i - 1];
    399         cur[i] = cur[i - 1];
    400         last[i] = last[i - 1];
    401         if(cur[i] > e.y) {
    402             ans[idx[e]] = 1;
    403             total[i] += (cur[i] - 1) * (last[i] - e.x);
    404             cur[i] = e.y;
    405             last[i] = e.x;
    406         }
    407     }
    408     cout << total[k] << "\n";
    409     for(int i = 1; i <= k; ++i){
    410         auto e = a[i - 1];
    411         if(ans[idx[e]] == 0)continue;
    412         int tot = total[i - 1];
    413         int cr = cur[i - 1];
    414         int lst = last[i - 1];
    415         for(int j = i + 1; j <= k; ++j){
    416             auto ee = a[j - 1];
    417             if(cr > ee.y){
    418                 tot += (cr - 1) * (lst - ee.x);
    419                 cr = ee.y;
    420                 lst = ee.x;
    421             }
    422             if(ans[idx[ee]] == 1){
    423                 ans[idx[e]] = tot - total[j];
    424                 break;
    425             }
    426         }
    427     }
    428     ans.pop_back();
    429     for(int e: ans) cout << e << " ";
    430 }
    431  
    432 bool multi = true;
    433  
    434 signed main() {
    435     int t = 1;
    436     if (multi)cin >> t;
    437     for (int i = 1; i <= t; ++i) {
    438         solve(i);
    439         cout << "\n";
    440     }
    441     return 0;
    442 }
    443 ```
    444 
    445 [1980G - Yasya and the Mysterious Tree](/contest/1980/problem/G "Codeforces Round 950 (Div. 3)")
    446 
    447 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40")
    448 
    449 **Tutorial**
    450 
    451 Tutorial is loading...
    452 
    453 **Solution**
    454 
    455 ```
    456 #include <bits/stdc++.h>
    457 using namespace std;
    458  
    459 struct trie {
    460     int l, c;
    461     vector<array<int, 2>> node;
    462     vector<int> cnt;
    463     trie(int l, int max_members) : l(l), c(0), node((l + 2) * max_members + 3), cnt((l + 2) * max_members + 3) {}
    464     void add(int x) {
    465         int cur = 0;
    466         for (int i = l; i >= 0; --i) {
    467             bool has_bit = (1 << i) & x;
    468             if (!node[cur][has_bit]) {
    469                 node[cur][has_bit] = ++c;
    470             }
    471             cur = node[cur][has_bit];
    472             ++cnt[cur];
    473         }
    474     }
    475     void remove(int x) {
    476         int cur = 0;
    477         for (int i = l; i >= 0; --i) {
    478             bool has_bit = (1 << i) & x;
    479             if (!node[cur][has_bit]) {
    480                 node[cur][has_bit] = ++c;
    481             }
    482             cur = node[cur][has_bit];
    483             --cnt[cur];
    484         }
    485     }
    486     int find_max(int x) {
    487         int cur = 0, ans = 0;
    488         for (int i = l; i >= 0; --i) {
    489             bool has_bit = (1 << i) & x;
    490             if (node[cur][!has_bit] && cnt[node[cur][!has_bit]]) {
    491                 ans += 1 << i;
    492                 cur = node[cur][!has_bit];
    493             }
    494             else {
    495                 cur = node[cur][has_bit];
    496             }
    497         }
    498         return ans;
    499     }
    500 };
    501  
    502 const int N = 2e5 + 2;
    503 int x[N];
    504 bitset<N> dp;
    505 vector<array<int, 2>> e[N];
    506  
    507 void dfs(int c, int p) {
    508     for (auto [i, w] : e[c]) {
    509         if (i == p) {
    510             continue;
    511         }
    512         dp[i] = !dp[c];
    513         x[i] = x[c] ^ w;
    514         dfs(i, c);
    515     }
    516 }
    517  
    518 void solve() {
    519     int n, m, gx = 0;
    520     cin >> n >> m;
    521     for (int i = 1; i <= n; ++i) {
    522         e[i].clear();
    523     }
    524     for (int i = 1, u, v, w; i < n; ++i) {
    525         cin >> u >> v >> w;
    526         e[u].push_back({v, w});
    527         e[v].push_back({u, w});
    528     }
    529     dfs(1, 0);
    530     vector<trie> t(2, trie(30, n));
    531     for (int i = 1; i <= n; ++i) {
    532         t[dp[i]].add(x[i]);
    533     }
    534     while (m--) {
    535         char c;
    536         cin >> c;
    537         if (c == '^') {
    538             int y;
    539             cin >> y;
    540             gx ^= y;
    541         }
    542         else {
    543             int a, b;
    544             cin >> a >> b;
    545             t[dp[a]].remove(x[a]);
    546             int same_group = t[dp[a]].find_max(x[a] ^ b);
    547             int diff_group = t[1 - dp[a]].find_max(x[a] ^ b ^ gx);
    548             t[dp[a]].add(x[a]);
    549             cout << max(same_group, diff_group) << "\n";
    550         }
    551     }
    552 }
    553  
    554 int main() {
    555     ios_base::sync_with_stdio(0); cin.tie(0);
    556     int t;
    557     cin >> t;
    558     while (t--) {
    559         solve();
    560     }
    561     return 0;
    562 }
    563 ```