codeforces-scrape

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

1701.md (9372B)


      1 Source: https://codeforces.com/blog/entry/104671
      2 
      3 [1701A - Grass Field](/contest/1701/problem/A "Educational Codeforces Round 131 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     a = [list(map(int, input().split())) for i in range(2)]
     16     cnt = sum([sum(a[i]) for i in range(2)])
     17     if cnt == 0:
     18         print(0)
     19     elif cnt == 4:
     20         print(2)
     21     else:
     22         print(1)
     23 ```
     24 
     25 [1701B - Permutation](/contest/1701/problem/B "Educational Codeforces Round 131 (Rated for Div. 2)")
     26 
     27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     28 
     29 **Tutorial**
     30 
     31 Tutorial is loading...
     32 
     33 **Solution (Neon)**
     34 
     35 ```
     36 #include <bits/stdc++.h>
     37 
     38 using namespace std;
     39 
     40 int main() {
     41   ios::sync_with_stdio(false); cin.tie(0);
     42   int t;
     43   cin >> t;
     44   while (t--) {
     45     int n;
     46     cin >> n;
     47     cout << 2 << '\n';
     48     for (int i = 1; i <= n; ++i) if (i % 2 != 0)
     49       for (int j = i; j <= n; j *= 2)
     50         cout << j << ' ';
     51     cout << '\n';
     52   }
     53 }
     54 ```
     55 
     56 [1701C - Schedule Management](/contest/1701/problem/C "Educational Codeforces Round 131 (Rated for Div. 2)")
     57 
     58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     59 
     60 **Tutorial**
     61 
     62 Tutorial is loading...
     63 
     64 **Solution (awoo)**
     65 
     66 ```
     67 #include <bits/stdc++.h>
     68 
     69 #define forn(i, n) for (int i = 0; i < int(n); i++)
     70 
     71 using namespace std;
     72 
     73 int main() {
     74 	int t;
     75 	scanf("%d", &t);
     76 	while (t--){
     77 		int n, m;
     78 		scanf("%d%d", &n, &m);
     79 		vector<int> a(m);
     80 		forn(i, m){
     81 			scanf("%d", &a[i]);
     82 			--a[i];
     83 		}
     84 		vector<int> cnt(n);
     85 		forn(i, m) ++cnt[a[i]];
     86 		auto check = [&](int t){
     87 			long long fr = 0, need = 0;
     88 			forn(i, n){
     89 				if (t >= cnt[i])
     90 					fr += (t - cnt[i]) / 2;
     91 				else
     92 					need += cnt[i] - t;
     93 			}
     94 			return need <= fr;
     95 		};
     96 		int l = 0, r = 2 * m;
     97 		int res = -1;
     98 		while (l <= r){
     99 			int m = (l + r) / 2;
    100 			if (check(m)){
    101 				res = m;
    102 				r = m - 1;
    103 			}
    104 			else{
    105 				l = m + 1;
    106 			}
    107 		}
    108 		printf("%d\n", res);
    109 	}
    110 	return 0;
    111 }
    112 ```
    113 
    114 [1701D - Permutation Restoration](/contest/1701/problem/D "Educational Codeforces Round 131 (Rated for Div. 2)")
    115 
    116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    117 
    118 **Tutorial**
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (Neon)**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126 
    127 using namespace std;
    128 
    129 int main() {
    130   ios::sync_with_stdio(false); cin.tie(0);
    131   int t;
    132   cin >> t;
    133   while (t--) {
    134     int n;
    135     cin >> n;
    136     vector<int> a(n), b(n);
    137     for (int& x : b) cin >> x;
    138     vector<pair<int, int>> ev(n);
    139     for (int i = 0; i < n; ++i)
    140       ev[i] = {(i + 1) / (b[i] + 1) + 1, i};
    141     sort(ev.begin(), ev.end());
    142     set<pair<int, int>> s;
    143     int j = 0;
    144     for (int i = 1; i <= n; ++i) {
    145       while (j < n && ev[j].first == i) {
    146         int id = ev[j++].second;
    147         s.insert({b[id] ? (id + 1) / b[id] : n, id});
    148       }
    149       a[s.begin()->second] = i;
    150       s.erase(s.begin());
    151     }
    152     for (int& x : a) cout << x << ' ';
    153     cout << '\n';
    154   }
    155 }
    156 ```
    157 
    158 [1701E - Text Editor](/contest/1701/problem/E "Educational Codeforces Round 131 (Rated for Div. 2)")
    159 
    160 Idea: [vovuh](/profile/vovuh "Master vovuh")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution (vovuh)**
    167 
    168 ```
    169 #include <bits/stdc++.h>
    170 
    171 using namespace std;
    172 
    173 vector<int> zf(const string &s) {
    174     int n = s.size();
    175     vector<int> z(n);
    176     int l = 0, r = 0;
    177     for (int i = 1; i < n; ++i) {
    178         if (i <= r) {
    179             z[i] = min(r - i + 1, z[i - l]);
    180         }
    181         while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
    182             ++z[i];
    183         }
    184         if (i + z[i] - 1 > r) {
    185             l = i;
    186             r = i + z[i] - 1;
    187         }
    188     }
    189     return z;
    190 }
    191 
    192 int main() {
    193 #ifdef _DEBUG
    194     freopen("input.txt", "r", stdin);
    195 //  freopen("output.txt", "w", stdout);
    196 #endif
    197     
    198     int T;
    199     cin >> T;
    200     while (T--) {
    201         int n, m;
    202         string s, t;
    203         cin >> n >> m >> s >> t;
    204         
    205         int ans = 1e9;
    206         
    207         bool bad = false;
    208         vector<int> lpos(m), rpos(m);
    209         for (int i = 0; i < m; ++i) {
    210             if (i > 0) {
    211                 lpos[i] = lpos[i - 1] + 1;
    212             } else {
    213                 lpos[i] = 0;
    214             }
    215             while (lpos[i] < n && s[lpos[i]] != t[i]) {
    216                 ++lpos[i];
    217             }
    218             if (lpos[i] >= n) {
    219                 bad = true;
    220                 break;
    221             }
    222         }
    223         for (int i = m - 1; i >= 0; --i) {
    224             if (i + 1 < m) {
    225                 rpos[i] = rpos[i + 1] - 1;
    226             } else {
    227                 rpos[i] = n - 1;
    228             }
    229             while (rpos[i] >= 0 && s[rpos[i]] != t[i]) {
    230                 --rpos[i];
    231             }
    232             if (rpos[i] < 0) {
    233                 bad = true;
    234                 break;
    235             }
    236         }
    237         if (bad) {
    238             cout << -1 << endl;
    239             continue;
    240         }
    241         
    242         for (int pos = 0; pos <= n; ++pos) {
    243             string tmp = s.substr(0, pos);
    244             reverse(tmp.begin(), tmp.end());
    245             tmp += "#" + t;
    246             reverse(tmp.begin() + pos + 1, tmp.end());
    247             vector<int> z = zf(tmp);
    248             for (int suf = 0; suf <= m; ++suf) {
    249                 if (pos - suf < 0) {
    250                     continue;
    251                 }
    252                 if (suf < m && rpos[suf] < pos) {
    253                     continue;
    254                 }
    255                 if (suf - 1 >= 0 && lpos[suf - 1] > pos) {
    256                     continue;
    257                 }
    258                 int rg = 0;
    259                 if (suf != 0) {
    260                     int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf);
    261                     rg = (sum != 0) + sum;
    262                 } else {
    263                     rg = pos;
    264                 }
    265                 ans = min(ans, (n - pos) + rg);
    266             }
    267         }
    268         cout << ans << endl;
    269     }
    270     
    271     return 0;
    272 }
    273 ```
    274 
    275 [1701F - Points](/contest/1701/problem/F "Educational Codeforces Round 131 (Rated for Div. 2)")
    276 
    277 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    278 
    279 **Tutorial**
    280 
    281 Tutorial is loading...
    282 
    283 **Solution (BledDest)**
    284 
    285 ```
    286 #include<bits/stdc++.h>
    287 
    288 using namespace std;
    289 
    290 const int N = 200043;
    291 const int M = 200001;
    292 
    293 typedef array<long long, 3> vec;
    294 typedef array<vec, 3> mat;
    295 
    296 vec operator+(const vec& a, const vec& b)
    297 {
    298     vec c;
    299     for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
    300     return c;
    301 }
    302 
    303 vec operator-(const vec& a, const vec& b)
    304 {
    305     vec c;
    306     for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
    307     return c;
    308 }
    309 
    310 vec operator*(const mat& a, const vec& b)
    311 {
    312     vec c;
    313     for(int i = 0; i < 3; i++) c[i] = 0;
    314     for(int i = 0; i < 3; i++)
    315         for(int j = 0; j < 3; j++)
    316             c[i] += a[i][j] * b[j];
    317     return c;
    318 }
    319 
    320 mat operator*(const mat& a, const mat& b)
    321 {
    322     mat c;
    323     for(int i = 0; i < 3; i++)
    324         for(int j = 0; j < 3; j++)
    325             c[i][j] = 0;
    326     for(int i = 0; i < 3; i++)
    327         for(int j = 0; j < 3; j++)
    328             for(int k = 0; k < 3; k++)
    329                 c[i][k] += a[i][j] * b[j][k];
    330     return c;
    331 }
    332 
    333 mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})};
    334 mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})};
    335 mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})};
    336 
    337 vec S = {1, 0, 0};
    338 vec Z = {0, 0, 0};
    339 
    340 vec t[4 * N];
    341 mat f[4 * N];
    342 bool active[4 * N];
    343 bool has[N];
    344 int d, q;
    345 
    346 vec getVal(int v)
    347 {
    348     if(!active[v]) return Z;
    349     return f[v] * t[v];
    350 }
    351 
    352 void recalc(int v)
    353 {
    354     t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);    
    355 }
    356 
    357 void build(int v, int l, int r)
    358 {
    359     if(l == r - 1)
    360     {
    361         f[v] = E;
    362         t[v] = S;
    363         active[v] = false;                 
    364     }
    365     else
    366     {
    367         int m = (l + r) / 2;
    368         build(v * 2 + 1, l, m);
    369         build(v * 2 + 2, m, r);
    370         f[v] = E;
    371         recalc(v);
    372         active[v] = true;               
    373     }
    374 }
    375 
    376 void push(int v)
    377 {
    378     if(f[v] == E) return;
    379     t[v] = f[v] * t[v];
    380     f[v * 2 + 1] = f[v] * f[v * 2 + 1];
    381     f[v * 2 + 2] = f[v] * f[v * 2 + 2];
    382     f[v] = E;
    383 }
    384 
    385 void updSegment(int v, int l, int r, int L, int R, bool adv)
    386 {
    387     if(L >= R) return;
    388     if(l == L && r == R)
    389     {
    390         if(adv) f[v] = F * f[v];
    391         else f[v] = B * f[v];
    392         return;
    393     }
    394     push(v);
    395     int m = (l + r) / 2;
    396     updSegment(v * 2 + 1, l, m, L, min(m, R), adv);
    397     updSegment(v * 2 + 2, m, r, max(m, L), R, adv);
    398     recalc(v);
    399 }
    400 
    401 void setState(int v, int l, int r, int pos, bool val)
    402 {
    403     if(l == r - 1)
    404     {   
    405         active[v] = val;
    406         return;
    407     }
    408     push(v);
    409     int m = (l + r) / 2;
    410     if(pos < m)
    411         setState(v * 2 + 1, l, m, pos, val);
    412     else
    413         setState(v * 2 + 2, m, r, pos, val);
    414     recalc(v);
    415 }
    416 
    417 void addPoint(int x)
    418 {
    419     int lf = max(0, x - d);
    420     int rg = x;
    421     if(lf < rg)
    422         updSegment(0, 0, M, lf, rg, true);
    423     setState(0, 0, M, x, true);        
    424 }
    425 
    426 void delPoint(int x)
    427 {
    428     int lf = max(0, x - d);
    429     int rg = x;
    430     if(lf < rg)
    431         updSegment(0, 0, M, lf, rg, false);
    432     setState(0, 0, M, x, false);        
    433 }
    434 
    435 void query(int x)
    436 {
    437     if(has[x])
    438     {
    439         has[x] = false;
    440         delPoint(x);
    441     }
    442     else
    443     {
    444         has[x] = true;
    445         addPoint(x);
    446     }
    447     vec res = getVal(0);
    448     printf("%lld\n", (res[2] - res[1]) / 2);
    449 }
    450 
    451 int main()
    452 {
    453     scanf("%d %d", &q, &d);
    454     build(0, 0, M);
    455     for(int i = 0; i < q; i++)
    456     {
    457         int x;
    458         scanf("%d", &x);
    459         query(x);
    460     }
    461 }
    462 ```