codeforces-scrape

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

1398.md (10095B)


      1 Source: https://codeforces.com/blog/entry/81506
      2 
      3 [1398A - Bad Triangle](/contest/1398/problem/A "Educational Codeforces Round 93 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     n = int(input())
     16     a = list(map(int, input().split()))
     17     if a[0] + a[1] > a[-1]:
     18         print(-1)
     19     else:
     20         print(1, 2, n)
     21 ```
     22 
     23 [1398B - Substring Removal Game](/contest/1398/problem/B "Educational Codeforces Round 93 (Rated for Div. 2)")
     24 
     25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (Ne0n25)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 
     36 using namespace std;
     37 
     38 #define sz(a) int((a).size())
     39 #define forn(i, n) for (int i = 0; i < int(n); ++i)
     40 
     41 void solve() {
     42 	string s;
     43 	cin >> s;
     44 	vector<int> a;
     45 	forn(i, sz(s)) if (s[i] == '1') {
     46 		int j = i;
     47 		while (j + 1 < sz(s) && s[j + 1] == '1')
     48 			++j;
     49 		a.push_back(j - i + 1);
     50 		i = j;
     51 	}
     52 	sort(a.rbegin(), a.rend());
     53 	int ans = 0;
     54 	for (int i = 0; i < sz(a); i += 2)
     55 		ans += a[i];
     56 	cout << ans << endl;
     57 }
     58 
     59 int main() {
     60 	int T;
     61 	cin >> T;
     62 	while (T--) solve();
     63 }
     64 ```
     65 
     66 [1398C - Good Subarrays](/contest/1398/problem/C "Educational Codeforces Round 93 (Rated for Div. 2)")
     67 
     68 Idea: [Roms](/profile/Roms "Master Roms")
     69 
     70 **Tutorial**
     71 
     72 Tutorial is loading...
     73 
     74 **Solution (Roms)**
     75 
     76 ```
     77 for _ in range(int(input())):
     78     n = int(input())
     79     a = input()
     80     d = {0 : 1}
     81     res, s = 0, 0
     82     
     83     for i in range(n):
     84         s += int(a[i])
     85         x = s - i - 1
     86         if x not in d:
     87             d[x] = 0
     88         d[x] += 1
     89         res += d[x] - 1
     90         
     91     print(res)
     92 ```
     93 
     94 [1398D - Colored Rectangles](/contest/1398/problem/D "Educational Codeforces Round 93 (Rated for Div. 2)")
     95 
     96 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution (pikmike)**
    103 
    104 ```
    105 n = [int(x) for x in input().split()]
    106 a = []
    107 for i in range(3):
    108 	a.append([int(x) for x in input().split()])
    109 	a[i].sort(reverse=True)
    110 
    111 dp = [[[0 for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)]
    112 ans = 0
    113 for i in range(n[0] + 1):
    114 	for j in range(n[1] + 1):
    115 		for k in range(n[2] + 1):
    116 			if i < n[0] and j < n[1]:
    117 				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + a[0][i] * a[1][j])
    118 			if i < n[0] and k < n[2]:
    119 				dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + a[0][i] * a[2][k])
    120 			if j < n[1] and k < n[2]:
    121 				dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + a[1][j] * a[2][k])
    122 			ans = max(ans, dp[i][j][k])
    123 
    124 print(ans)
    125 ```
    126 
    127 [1398E - Two Types of Spells](/contest/1398/problem/E "Educational Codeforces Round 93 (Rated for Div. 2)")
    128 
    129 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    130 
    131 **Tutorial**
    132 
    133 Tutorial is loading...
    134 
    135 **Solution (Roms)**
    136 
    137 ```
    138 #include <bits/stdc++.h>
    139 
    140 using namespace std;
    141 
    142 const int N = int(1e5) + 9;
    143 
    144 int n;
    145 set <int> sDouble;
    146 long long sum[2];
    147 set <int> s[2];
    148 int cntDouble[2];
    149 
    150 // 0: 0 -> 1
    151 // 1: 1 -> 0
    152 void upd(int id) {
    153     assert(s[id].size() > 0);
    154     int x = *s[id].rbegin();
    155     if (id == 1) x = *s[id].begin();
    156     bool d = sDouble.count(x);
    157     
    158     sum[id] -= x, sum[!id] += x;
    159     s[id].erase(x), s[!id].insert(x);
    160     cntDouble[id] -= d, cntDouble[!id] += d;
    161 }
    162 
    163 int main(){
    164     cin >> n;
    165     for (int i = 0; i < n; ++i) {
    166         int tp, x;
    167         cin >> tp >> x;// tp = 1 if double
    168         
    169         if (x > 0) {
    170             sum[0] += x;
    171             s[0].insert(x);
    172             cntDouble[0] += tp;
    173             if (tp) sDouble.insert(x);
    174         } else {
    175             x = -x;
    176             int id = 0;
    177             if (s[1].count(x)) id = 1;
    178             else assert(s[0].count(x));
    179             
    180             sum[id] -= x;
    181             s[id].erase(x);
    182             cntDouble[id] -= tp;
    183             if (tp) { 
    184                 assert(sDouble.count(x));
    185                 sDouble.erase(x);
    186             }
    187         }
    188         
    189         int sumDouble = cntDouble[0] + cntDouble[1];
    190         while (s[1].size() < sumDouble) upd(0);
    191         while (s[1].size() > sumDouble) upd(1);
    192         while (s[1].size() > 0 && s[0].size() > 0 && *s[0].rbegin() > *s[1].begin()) {
    193             upd(0);
    194             upd(1);
    195         }
    196         assert(s[1].size() == sumDouble);
    197         
    198         long long res = sum[0] + sum[1] * 2;
    199         if (cntDouble[1] == sumDouble && sumDouble > 0) {
    200             res -= *s[1].begin();
    201             if (s[0].size() > 0) res += *s[0].rbegin();
    202         }
    203         cout << res << endl;
    204     }
    205     return 0;
    206 }
    207 ```
    208 
    209 [1398F - Controversial Rounds](/contest/1398/problem/F "Educational Codeforces Round 93 (Rated for Div. 2)")
    210 
    211 Idea: [Roms](/profile/Roms "Master Roms")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution (Roms)**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 
    222 using namespace std;
    223 
    224 const int N = int(1e6) + 99;
    225 const int INF = int(1e9) + 99;
    226 
    227 int n;
    228 string s;
    229 vector <int> p[2][N];
    230 int nxt[2][N];
    231 int ptr[2];
    232 char buf[N];
    233 
    234 int main(){
    235     cin >> n >> s;
    236     
    237     for (int i = n - 1; i >= 0; --i) {
    238         if (s[i] != '0') nxt[0][i] = 1 + nxt[0][i + 1];
    239         if (s[i] != '1') nxt[1][i] = 1 + nxt[1][i + 1];
    240     }
    241     
    242     for (int b = 0; b <= 1; ++b) {
    243         int l = 0;
    244         while (l < n) {
    245             if (s[l] == char('0' + b)) {
    246                 ++l;
    247                 continue;
    248             }
    249             int r = l + 1;
    250             while (r < n && s[r] != char('0' + b)) ++r;
    251             for (int len = 1; len <= r - l; ++len)
    252                 p[b][len].push_back(l);
    253             l = r;
    254         }
    255     }
    256 
    257     for (int len = 1; len <= n; ++len) {
    258         int pos = 0, res = 0;
    259         ptr[0] = ptr[1] = 0;
    260         
    261         while (pos < n) {
    262             int npos = INF;
    263             for (int b = 0; b <= 1; ++b) {
    264                 if (nxt[b][pos] >= len) 
    265                     npos = min(npos, pos + len);
    266                 while (ptr[b] < p[b][len].size() && pos > p[b][len][ ptr[b] ]) 
    267                     ++ptr[b];
    268                 if (ptr[b] < p[b][len].size()) 
    269                     npos = min(npos, p[b][len][ ptr[b] ] + len);
    270             }
    271             if (npos != INF) 
    272                 ++res;
    273             pos = npos;
    274         }
    275         
    276         cout << res << ' ';
    277     }
    278     cout << endl;
    279     
    280     return 0;
    281 }
    282 ```
    283 
    284 [1398G - Running Competition](/contest/1398/problem/G "Educational Codeforces Round 93 (Rated for Div. 2)")
    285 
    286 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    287 
    288 **Tutorial**
    289 
    290 Tutorial is loading...
    291 
    292 **Solution (BledDest)**
    293 
    294 ```
    295 #include<bits/stdc++.h>
    296 
    297 using namespace std;
    298 
    299 #define forn(i, n) for(int i = 0; i < n; i++)
    300 #define sz(a) ((int)(a).size())
    301 
    302 const int LOGN = 20;
    303 const int N = (1 << LOGN);
    304 const int K = 200043;
    305 const int M = 1000043;
    306 
    307 typedef double ld;
    308 typedef long long li;
    309 
    310 const ld PI = acos(-1.0);
    311 
    312 struct comp 
    313 {
    314     ld x, y;
    315     comp(ld x = .0, ld y = .0) : x(x), y(y) {}
    316     inline comp conj() { return comp(x, -y); }
    317 };
    318 
    319 inline comp operator +(const comp &a, const comp &b) 
    320 {
    321     return comp(a.x + b.x, a.y + b.y);
    322 }
    323 
    324 inline comp operator -(const comp &a, const comp &b) 
    325 {
    326     return comp(a.x - b.x, a.y - b.y);
    327 }
    328 
    329 inline comp operator *(const comp &a, const comp &b) 
    330 {
    331     return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    332 }
    333 
    334 inline comp operator /(const comp &a, const ld &b) 
    335 {
    336     return comp(a.x / b, a.y / b);
    337 }
    338 
    339 vector<comp> w[LOGN];
    340 vector<int> rv[LOGN];
    341 
    342 void precalc() 
    343 {
    344     for(int st = 0; st < LOGN; st++) 
    345     {
    346         w[st].assign(1 << st, comp());
    347         for(int k = 0; k < (1 << st); k++) 
    348         {
    349             double ang = PI / (1 << st) * k;
    350             w[st][k] = comp(cos(ang), sin(ang));
    351         }
    352         
    353         rv[st].assign(1 << st, 0);
    354         if(st == 0) 
    355         {
    356             rv[st][0] = 0;
    357             continue;
    358         }
    359         int h = (1 << (st - 1));
    360         for(int k = 0; k < (1 << st); k++)
    361             rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    362     }
    363 }
    364 
    365 inline void fft(comp a[N], int n, int ln, bool inv) 
    366 {
    367     for(int i = 0; i < n; i++) 
    368     {
    369         int ni = rv[ln][i];
    370         if(i < ni)
    371             swap(a[i], a[ni]);
    372     }
    373     
    374     for(int st = 0; (1 << st) < n; st++) 
    375     {
    376         int len = (1 << st);
    377         for(int k = 0; k < n; k += (len << 1)) 
    378         {
    379             for(int pos = k; pos < k + len; pos++) 
    380             {
    381                 comp l = a[pos];
    382                 comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
    383                 
    384                 a[pos] = l + r;
    385                 a[pos + len] = l - r;
    386             }
    387         }
    388     }
    389     
    390     if(inv) for(int i = 0; i < n; i++)
    391         a[i] = a[i] / n;
    392 }
    393 
    394 comp aa[N];
    395 comp bb[N];
    396 comp cc[N];
    397 
    398 inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 
    399 {
    400     int n = 1, ln = 0;
    401     while(n < (sza + szb))
    402         n <<= 1, ln++;
    403     for(int i = 0; i < n; i++)
    404         aa[i] = (i < sza ? a[i] : comp());
    405     for(int i = 0; i < n; i++)
    406         bb[i] = (i < szb ? b[i] : comp());
    407         
    408     fft(aa, n, ln, false);
    409     fft(bb, n, ln, false);
    410     
    411     for(int i = 0; i < n; i++)
    412         cc[i] = aa[i] * bb[i];
    413         
    414     fft(cc, n, ln, true);
    415     
    416     szc = n;
    417     for(int i = 0; i < n; i++)
    418         c[i] = cc[i];
    419 }
    420 
    421 comp a[N];
    422 comp b[N];
    423 comp c[N];
    424 int used[M];
    425 int dp[M];
    426 
    427 int main()
    428 {
    429     precalc();
    430     int n, x, y;
    431     for(int i = 0; i < M; i++)
    432         dp[i] = -1;
    433     scanf("%d %d %d", &n, &x, &y);
    434     vector<int> A(n + 1);
    435     for(int i = 0; i <= n; i++)
    436         scanf("%d", &A[i]);
    437     for(int i = 0; i <= n; i++)
    438     {
    439         a[A[i]] = comp(1.0, 0.0);
    440         b[K - A[i]] = comp(1.0, 0.0);
    441     }
    442     int s = 0;
    443     multiply(a, K + 1, b, K + 1, c, s);
    444     for(int i = K + 1; i < s; i++)
    445         if(c[i].x > 0.5)
    446             used[(i - K + y) * 2] = 1;
    447     for(int i = 1; i < M; i++)
    448     {
    449         if(!used[i]) continue;
    450         for(int j = i; j < M; j += i)
    451             dp[j] = max(dp[j], i);
    452     }
    453     int q;
    454     scanf("%d", &q);
    455     for(int i = 0; i < q; i++)
    456     {
    457         int l;
    458         scanf("%d", &l);
    459         printf("%d ", dp[l]);
    460     }
    461 }
    462 ```