codeforces-scrape

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

1895.md (11632B)


      1 Source: https://codeforces.com/blog/entry/122034
      2 
      3 [1895A - Treasure Chest](/contest/1895/problem/A "Educational Codeforces Round 157 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     x, y, k = map(int, input().split())
     16     if y < x:
     17       print(x)
     18     else:
     19       print(y + max(0, y - x - k))
     20 ```
     21 
     22 [1895B - Points and Minimum Distance](/contest/1895/problem/B "Educational Codeforces Round 157 (Rated for Div. 2)")
     23 
     24 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (fcspartakm)**
     31 
     32 ```
     33 #include <bits/stdc++.h>
     34 
     35 using namespace std;
     36 
     37 int n;
     38 vector<int> a;
     39 
     40 inline void read() {
     41   cin >> n;
     42   a.clear();
     43   for (int i = 0; i < 2 * n; i++) {
     44       int x;
     45       cin >> x;
     46       a.pb(x);
     47   }
     48 }
     49 inline void solve() {
     50     sort(all(a));
     51     vector<pair<int, int> > pts;
     52     for (int i = 0; i < n; i++) {
     53         pts.pb(mp(a[i], a[i + n]));
     54     }
     55     int ans = 0;
     56     for (int i = 1; i < n; i++) {
     57         ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc);
     58     }
     59     cout << ans << endl;
     60     for (int i = 0; i < n; i++) {
     61         cout << pts[i].ft << ' ' << pts[i].sc << endl;
     62     }
     63 }
     64  
     65 int main () {
     66     int t;
     67     cin >> t;
     68     while (t--){
     69         read();
     70         solve();
     71     }
     72 }
     73 ```
     74 
     75 [1895C - Torn Lucky Ticket](/contest/1895/problem/C "Educational Codeforces Round 157 (Rated for Div. 2)")
     76 
     77 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     78 
     79 **Tutorial**
     80 
     81 Tutorial is loading...
     82 
     83 **Solution (awoo)**
     84 
     85 ```
     86 n = int(input())
     87 s = input().split()
     88 ans = 0
     89 cnt = [[0 for k in range(46)] for k in range(6)]
     90 for y in s:
     91     cnt[len(y)][sum([int(c) for c in y])] += 1
     92 for L in s:
     93     for lenr in range(len(L) % 2, len(L) + 1, 2):
     94         l = len(L) + lenr
     95         suml = sum([int(c) for c in L[:l // 2]])
     96         sumr = sum([int(c) for c in L[l // 2:]])
     97         if suml - sumr >= 0:
     98             ans += cnt[lenr][suml - sumr]
     99 for R in s:
    100     for lenl in range(len(R) % 2, len(R), 2):
    101         l = len(R) + lenl
    102         suml = sum([int(c) for c in R[-l // 2:]])
    103         sumr = sum([int(c) for c in R[:-l // 2]])
    104         if suml - sumr >= 0:
    105             ans += cnt[lenl][suml - sumr]
    106 print(ans)
    107 ```
    108 
    109 [1895D - XOR Construction](/contest/1895/problem/D "Educational Codeforces Round 157 (Rated for Div. 2)")
    110 
    111 Idea: [AcidWrongGod](/profile/AcidWrongGod "International Master AcidWrongGod")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (Neon)**
    118 
    119 ```
    120 #include <bits/stdc++.h>
    121  
    122 using namespace std;
    123 
    124 const int LOG = 20;
    125 
    126 int main() {
    127   ios::sync_with_stdio(false); cin.tie(0);
    128   int n;
    129   cin >> n;
    130   vector<int> a(n);
    131   for (int i = 1; i < n; ++i) {
    132     cin >> a[i];
    133     a[i] ^= a[i - 1];
    134   }
    135   vector<array<int, 2>> t({{-1, -1}});
    136   auto add = [&](int x) {
    137     int v = 0;
    138     for (int i = LOG - 1; i >= 0; --i) {
    139       int j = (x >> i) & 1;
    140       if (t[v][j] == -1) {
    141         t[v][j] = t.size();
    142         t.push_back({-1, -1});
    143       }
    144       v = t[v][j];
    145     }
    146   };  
    147   for (int x : a) add(x);
    148   auto get = [&](int x) {
    149     int v = 0;
    150     for (int i = LOG - 1; i >= 0; --i) {
    151       int j = (x >> i) & 1;
    152       if (t[v][j ^ 1] != -1) j ^= 1;
    153       x ^= j << i;
    154       v = t[v][j];
    155     }
    156     return x;
    157   };
    158   for (int x = 0; x < n; ++x) {
    159     if (get(x) == n - 1) {
    160       for (int i : a) cout << (x ^ i) << ' ';
    161       break;
    162     }
    163   }
    164 }
    165 ```
    166 
    167 [1895E - Infinite Card Game](/contest/1895/problem/E "Educational Codeforces Round 157 (Rated for Div. 2)")
    168 
    169 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    170 
    171 **Tutorial**
    172 
    173 Tutorial is loading...
    174 
    175 **Solution (awoo)**
    176 
    177 ```
    178 //
    179 
    180 #include <bits/stdc++.h>
    181 
    182 #define forn(i, n) for (int i = 0; i < int(n); i++)
    183 
    184 using namespace std;
    185 
    186 struct card{
    187   int x, y;
    188   card() {}
    189   card(int x, int y) : x(x), y(y) {}
    190 };
    191 
    192 void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){
    193   if (used[v]) return;
    194   used[v] = true;
    195   dfs(g[v], g, res, used);
    196   res[v] = -res[g[v]];
    197 }
    198 
    199 void solve(){
    200   vector<vector<card>> a(2);
    201   vector<vector<int>> prpos(2);
    202   forn(z, 2){
    203     int n;
    204     scanf("%d", &n);
    205     a[z].resize(n);
    206     forn(i, n) scanf("%d", &a[z][i].x);
    207     forn(i, n) scanf("%d", &a[z][i].y);
    208     sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){
    209       return a.x > b.x;
    210     });
    211     prpos[z].resize(n + 1, -1);
    212     forn(i, n){
    213       if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y)
    214         prpos[z][i + 1] = i;
    215       else
    216         prpos[z][i + 1] = prpos[z][i];
    217     }
    218   }
    219   int n = a[0].size();
    220   vector<int> g(n + a[1].size());
    221   forn(z, 2) forn(i, a[z].size()){
    222     int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){
    223       return a.x > b.x;
    224     }) - a[z ^ 1].begin();
    225     g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n;
    226   }
    227   vector<int> res(g.size());
    228   vector<char> used(g.size());
    229   forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true;
    230   int w = 0, l = 0;
    231   forn(i, n){
    232     if (!used[i]) dfs(i, g, res, used);
    233     w += res[i] == 1;
    234     l += res[i] == -1;
    235   }
    236   printf("%d %d %d\n", w, n - l - w, l);
    237 }
    238 
    239 int main(){
    240   int t;
    241   scanf("%d", &t);
    242   while (t--) solve();
    243 }
    244 ```
    245 
    246 [1895F - Fancy Arrays](/contest/1895/problem/F "Educational Codeforces Round 157 (Rated for Div. 2)")
    247 
    248 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    249 
    250 **Tutorial**
    251 
    252 Tutorial is loading...
    253 
    254 **Solution (Neon)**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258  
    259 using namespace std;
    260 
    261 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    262 
    263 const int MOD = 1e9 + 7;
    264 const int N = 40;
    265 
    266 using mat = array<array<int, N>, N>;
    267 
    268 int add(int x, int y) {
    269   x += y;
    270   if (x >= MOD) x -= MOD;
    271   if (x < 0) x += MOD;
    272   return x;
    273 }
    274 
    275 int mul(int x, int y) {
    276   return x * 1LL * y % MOD;
    277 }
    278 
    279 mat mul(mat x, mat y) {
    280   mat res;
    281   forn(i, N) forn(j, N) res[i][j] = 0;
    282   forn(i, N) forn(j, N) forn(k, N)
    283     res[i][j] = add(res[i][j], mul(x[i][k], y[k][j]));
    284   return res;
    285 }
    286 
    287 template<class T>
    288 T binpow(T x, int y, T e) {
    289   T res = e;
    290   while (y) {
    291     if (y & 1) res = mul(res, x);
    292     x = mul(x, x);
    293     y >>= 1;
    294   }
    295   return res;
    296 }
    297 
    298 int main() {
    299   int t;
    300   cin >> t;
    301   while (t--) {
    302     int n, x, k;
    303     cin >> n >> x >> k;
    304     mat a, e;
    305     forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k);
    306     forn(i, N) forn(j, N) e[i][j] = (i == j);
    307     mat b = binpow(a, n - 1, e);
    308     int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1));
    309     forn(i, x) forn(j, x) ans = add(ans, -b[i][j]);
    310     cout << ans << '\n';
    311   }
    312 }
    313 ```
    314 
    315 [1895G - Two Characters, Two Colors](/contest/1895/problem/G "Educational Codeforces Round 157 (Rated for Div. 2)")
    316 
    317 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    318 
    319 **Tutorial**
    320 
    321 Tutorial is loading...
    322 
    323 **Solution (BledDest)**
    324 
    325 ```
    326 #include<bits/stdc++.h>
    327 
    328 using namespace std;
    329 
    330 mt19937 rnd(42);
    331 
    332 struct node
    333 {
    334   long long x;
    335   int y;
    336   int cnt;
    337   int sum;
    338   int push;
    339   node* l;
    340   node* r;
    341   node() {};
    342   node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {};
    343 };
    344 
    345 typedef node* treap;
    346 typedef pair<treap, treap> ptt;
    347 
    348 int getSum(treap t)
    349 {
    350   return (t ? t->sum : 0);
    351 }
    352 
    353 int getCnt(treap t)
    354 {
    355   return (t ? t->cnt : 0);
    356 }
    357 
    358 treap fix(treap t)
    359 {
    360   if(!t) return t;
    361   int p = t->push;
    362   if(p != 0)
    363   {
    364     if(t->l) t->l->push += p;
    365     if(t->r) t->r->push += p;
    366     t->x += p;
    367     t->push = 0;
    368   }
    369   t->sum = getSum(t->l) + t->cnt + getSum(t->r);
    370   return t;
    371 }
    372 
    373 treap merge(treap a, treap b)
    374 {
    375   a = fix(a);
    376   b = fix(b);
    377   if(!a) return b;
    378   if(!b) return a;
    379   if(a->y > b->y)
    380   {
    381     a->r = merge(a->r, b);
    382     return fix(a);
    383   }
    384   else
    385   {
    386     b->l = merge(a, b->l);
    387     return fix(b);
    388   }
    389 }
    390 
    391 bool hasKey(treap t, long long x)
    392 {
    393   t = fix(t);
    394   if(!t) return false;
    395   if(t->x == x) return true;
    396   if(t->x < x) return hasKey(t->r, x);
    397   return hasKey(t->l, x);
    398 }
    399 
    400 ptt splitKey(treap t, long long x)
    401 {
    402   t = fix(t);
    403   if(!t) return make_pair(t, t);
    404   if(t->x < x)
    405   {
    406     ptt p = splitKey(t->r, x);
    407     t->r = p.first;
    408     return make_pair(fix(t), p.second);
    409   }
    410   else
    411   {
    412     ptt p = splitKey(t->l, x);
    413     t->l = p.second;
    414     return make_pair(p.first, fix(t));
    415   }
    416 }
    417 
    418 long long kthMax(treap t, int k)
    419 {
    420   t = fix(t);
    421   if(!t) return -1;
    422   int sumR = getSum(t->r);
    423   if(sumR >= k) return kthMax(t->r, k);
    424   if(sumR + t->cnt >= k) return t->x;
    425   return kthMax(t->l, k - sumR - t->cnt);
    426 }
    427 
    428 int getCntByKey(treap t, long long x)
    429 {
    430   t = fix(t);
    431   if(!t) return 0;
    432   if(t->x == x) return t->cnt;
    433   if(t->x > x) return getCntByKey(t->l, x);
    434   return getCntByKey(t->r, x);
    435 }
    436 
    437 treap increaseKey(treap t, long long x, int cnt)
    438 {
    439   t = fix(t);
    440   if(!t) return t;
    441   if(t->x == x)
    442   {
    443     t->cnt += cnt;
    444   }
    445   else if(t->x > x)
    446   {
    447     t->l = increaseKey(t->l, x, cnt);
    448   }
    449   else
    450   {
    451     t->r = increaseKey(t->r, x, cnt);
    452   }
    453   return fix(t);
    454 }
    455 
    456 treap insert(treap t, long long x, int y, int cnt)
    457 {
    458   t = fix(t);
    459   if(!t || t->y < y)
    460   {
    461     ptt p = splitKey(t, x);
    462     treap res = new node(x, y, cnt, cnt, 0, p.first, p.second);
    463     return fix(res);
    464   }
    465   if(t->x > x)
    466     t->l = insert(t->l, x, y, cnt);
    467   else
    468     t->r = insert(t->r, x, y, cnt);
    469   return fix(t);
    470 }
    471 
    472 treap insertMain(treap t, long long x, int cnt)
    473 {
    474   if(hasKey(t, x))
    475     return increaseKey(t, x, cnt);
    476   else
    477     return insert(t, x, rnd(), cnt);
    478 }
    479 
    480 treap eraseKey(treap t, long long x)
    481 {
    482   t = fix(t);
    483   if(!t) return NULL;
    484   if(t->x > x)
    485   {
    486     t->l = eraseKey(t->l, x);
    487     return fix(t);
    488   }
    489   if(t->x < x)
    490   {
    491     t->r = eraseKey(t->r, x);
    492     return fix(t);
    493   }
    494   treap tnew = merge(t->l, t->r);
    495   delete t;
    496   return tnew;
    497 }
    498 
    499 ptt splitSum(treap t, int k)
    500 {
    501   t = fix(t);
    502   if(!t) return make_pair(t, t);
    503   if(k == 0) return make_pair(t, treap(NULL));
    504   long long x = kthMax(t, k);
    505   int cnt = getCntByKey(t, x);
    506   t = eraseKey(t, x);
    507   ptt p = splitKey(t, x);
    508   k -= getSum(p.second);
    509   if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second);
    510   if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL));
    511   return p;
    512 }
    513 
    514 long long minKey(treap t)
    515 {
    516   t = fix(t);
    517   if(!t) return 1e18;
    518   if(t->l) return minKey(t->l);
    519   return t->x;
    520 }
    521 
    522 treap decreaseUpToKLargest(treap t, int k, int& res)
    523 {
    524   if(!k) return t;
    525   t = fix(t);
    526   k = min(k, getSum(t));
    527   res = k;
    528   ptt p = splitSum(t, k);
    529   if(p.second)
    530   {
    531     p.second->push--;
    532     for(int i = 0; i < 2; i++)
    533     {
    534         long long x = minKey(p.second);
    535         int cntMin = getCntByKey(p.second, x);
    536         p.second = eraseKey(p.second, x);
    537         if(x != 0 && cntMin != 0)
    538           p.first = insertMain(p.first, x, cntMin);
    539     }
    540   }
    541   return merge(p.first, p.second);
    542 }
    543 
    544 void destroy(treap t)
    545 {
    546   if(!t) return;
    547   if(t->l) destroy(t->l);
    548   if(t->r) destroy(t->r);
    549   delete t;
    550 }
    551 
    552 void solve()
    553 {
    554   int n;
    555   cin >> n;
    556   string s;
    557   cin >> s;
    558   vector<long long> r(n), b(n);
    559   for(int i = 0; i < n; i++) cin >> r[i];
    560   for(int i = 0; i < n; i++) cin >> b[i];
    561   long long sum = 0;
    562   for(int i = 0; i < n; i++) sum += r[i] + b[i];
    563   long long flow = 0;
    564   treap t = NULL;
    565   for(int i = 0; i < n; i++)
    566   {
    567     long long d = min(r[i], b[i]);
    568     flow += d;
    569     r[i] -= d;
    570     b[i] -= d;
    571     if(s[i] == '0')
    572     {
    573       int add = 0;
    574       if(r[i] > 1e9) r[i] = 1e9;
    575       t = decreaseUpToKLargest(t, r[i], add);
    576       flow += add;
    577     }
    578     else
    579     {
    580       if(r[i] != 0) t = insertMain(t, r[i], 1);
    581     }
    582   }
    583   cout << sum - flow << endl;
    584 }
    585 
    586 int main()
    587 {
    588   ios_base::sync_with_stdio(0);
    589   cin.tie(0);
    590   int t;
    591   cin >> t;
    592   for(int i = 0; i < t; i++) solve();
    593 }
    594 ```