codeforces-scrape

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

1582.md (7233B)


      1 Source: https://codeforces.com/blog/entry/96267
      2 
      3 [1582A - Luntik and Concerts](/contest/1582/problem/A "Codeforces Round 750 (Div. 2)")
      4 
      5 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (74TrAkToR)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 main() {
     19     ios_base::sync_with_stdio(0);
     20     cin.tie(0);
     21     cout.tie(0);
     22     int t, a, b, c;
     23     cin >> t;
     24     while (t--) {
     25         cin >> a >> b >> c;
     26         cout << (a + c) % 2 << '\n';
     27     }
     28     return 0;
     29 }
     30 ```
     31 
     32 [1582B - Luntik and Subsequences](/contest/1582/problem/B "Codeforces Round 750 (Div. 2)")
     33 
     34 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (74TrAkToR)**
     41 
     42 ```
     43 #include<bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 typedef long long ll;
     48 
     49 int main() {
     50     ios_base::sync_with_stdio(0);
     51     cin.tie(0);
     52     cout.tie(0);
     53     int t, n, x;
     54     cin >> t;
     55     while (t--) {
     56         cin >> n;
     57         int cnt0 = 0, cnt1 = 0;
     58         for (int i = 1; i <= n; ++i) {
     59             cin >> x;
     60             if (x == 0) cnt0++;
     61             if (x == 1) cnt1++;
     62         }
     63         cout << (1ll << cnt0) * (ll)cnt1 << '\n';
     64     }
     65     return 0;
     66 }
     67 ```
     68 
     69 [1582C - Grandma Capa Knits a Scarf](/contest/1582/problem/C "Codeforces Round 750 (Div. 2)")
     70 
     71 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution (74TrAkToR)**
     78 
     79 ```
     80 #include<bits/stdc++.h>
     81 
     82 using namespace std;
     83 
     84 int main() {
     85     ios_base::sync_with_stdio(0);
     86     cin.tie(0);
     87     cout.tie(0);
     88     int t, n;
     89     cin >> t;
     90     while (t--) {
     91         string s;
     92         cin >> n >> s;
     93         int ans = n + 1;
     94         for (int c = 0; c < 26; ++c) {
     95             int l = 0, r = n - 1, cnt = 0;
     96             while (l <= r) {
     97                 if (s[l] == s[r]) {
     98                     l++, r--;
     99                 }
    100                 else if (s[l] == char('a' + c)) {
    101                     cnt++, l++;
    102                 }
    103                 else if (s[r] == char('a' + c)) {
    104                     cnt++, r--;
    105                 }
    106                 else {
    107                     cnt = n + 1;
    108                     break;
    109                 }
    110             }
    111             ans = min(ans, cnt);
    112         }
    113         if (ans == n + 1) ans = -1;
    114         cout << ans << '\n';
    115     }
    116     return 0;
    117 }
    118 ```
    119 
    120 [1582D - Vupsen, Pupsen and 0](/contest/1582/problem/D "Codeforces Round 750 (Div. 2)")
    121 
    122 Idea: [AlFlen](/profile/AlFlen "Master AlFlen")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Solution (AlFlen)**
    129 
    130 ```
    131 ttt = int(input())
    132 for t in range(ttt):
    133 	n = int(input())
    134 	a = [int(x) for x in input().split()]
    135 	start = 0
    136 	if n % 2 == 1:
    137 		if (a[0] + a[1] != 0):
    138 			print(-a[2], -a[2], a[0] + a[1], end = " ")
    139 		elif (a[1] + a[2] != 0):
    140 			print(a[2] + a[1], -a[0], -a[0], end = " ")
    141 		else:
    142 			print(-a[1], a[0] + a[2], -a[1], end = " ")
    143 		start = 3
    144 	while start < n:
    145 		print(-a[s + 1], a[s], end = " ")
    146 		start += 2
    147 	print()
    148 ```
    149 
    150 [1582E - Pchelyonok and Segments](/contest/1582/problem/E "Codeforces Round 750 (Div. 2)")
    151 
    152 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (74TrAkToR)**
    159 
    160 ```
    161 #include<bits/stdc++.h>
    162 
    163 using namespace std;
    164 
    165 typedef long long ll;
    166 int const maxn = 1e5 + 5, maxk = 450;
    167 int a[maxn], dp[maxn][maxk];
    168 int inf = 1e9 + 7;
    169 ll pref[maxn];
    170 
    171 main() {
    172     ios_base::sync_with_stdio(0);
    173     cin.tie(0);
    174     cout.tie(0);
    175     int t, n;
    176     cin >> t;
    177     while (t--) {
    178         cin >> n;
    179         for (int i = 1; i <= n; ++i) {
    180             cin >> a[i];
    181             pref[i] = pref[i - 1] + a[i];
    182         }
    183         int k = 0;
    184         while (k * (k + 1) / 2 <= n) k++;
    185         for (int j = 0; j < k; ++j) {
    186             dp[n + 1][j] = -inf;
    187         }
    188         dp[n + 1][0] = inf;
    189         for (int i = n; i >= 1; --i) {
    190             for (int j = 0; j < k; ++j) {
    191                 dp[i][j] = dp[i + 1][j];
    192                 if (j && i + j - 1 <= n && pref[i + j - 1] - pref[i - 1] < dp[i + j][j - 1]) {
    193                     dp[i][j] = max(dp[i][j], (int)(pref[i + j - 1] - pref[i - 1]));
    194                 }
    195             }
    196         }
    197         int ans = 0;
    198         for (int j = 0; j < k; ++j) {
    199             if (dp[1][j] > 0) ans = j;
    200         }
    201         cout << ans << '\n';
    202     }
    203     return 0;
    204 }
    205 ```
    206 
    207 [1582F2 - Korney Korneevich and XOR (hard version)](/contest/1582/problem/F2 "Codeforces Round 750 (Div. 2)")
    208 
    209 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution (74TrAkToR)**
    216 
    217 ```
    218 #include<bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 int const max_value = (1 << 13);
    223 vector < int > g[max_value];
    224 int ans[max_value], r[max_value];
    225 
    226 int main() {
    227     ios_base::sync_with_stdio(0);
    228     cin.tie(0);
    229     cout.tie(0);
    230     int n, x;
    231     cin >> n;
    232     ans[0] = 1;
    233     for (int i = 0; i < max_value; ++i) {
    234         g[i].push_back(0);
    235     }
    236     for (int i = 0; i < max_value; ++i) {
    237         r[i] = max_value;
    238     }
    239     for (int i = 1; i <= n; ++i) {
    240         cin >> x;
    241         for (auto key : g[x]) {
    242             int to = (key^x);
    243             ans[to] = 1;
    244             while (r[to] > x) {
    245                 r[to]--;
    246                 if (r[to] != x) g[r[to]].push_back(to);
    247             }
    248         }
    249         g[x] = {};
    250     }
    251     int k = 0;
    252     for (int i = 0; i < max_value; ++i) {
    253         k += ans[i];
    254     }
    255     cout << k << '\n';
    256     for (int i = 0; i < max_value; ++i) {
    257         if (ans[i]) cout << i << " ";
    258     }
    259     cout << '\n';
    260     return 0;
    261 }
    262 ```
    263 
    264 [1582G - Kuzya and Homework](/contest/1582/problem/G "Codeforces Round 750 (Div. 2)")
    265 
    266 Idea: [74TrAkToR](/profile/74TrAkToR "Grandmaster 74TrAkToR")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution (74TrAkToR)**
    273 
    274 ```
    275 #include<bits/stdc++.h>
    276 
    277 using namespace std;
    278 
    279 typedef long long ll;
    280 
    281 int const maxn = 1e6 + 5;
    282 int a[maxn];
    283 int prime[maxn];
    284 int L[maxn];
    285 vector < int > pos[maxn];
    286 
    287 inline void add(int x, int l) {
    288     L[l] = l;
    289     while (x > 1) {
    290         pos[prime[x]].push_back(l);
    291         x /= prime[x];
    292     }
    293 }
    294 
    295 inline void del(int x, int l) {
    296     if (x == 1) {
    297         L[l] = l;
    298         return;
    299     }
    300     L[l] = l;
    301     while (x > 1) {
    302         if ((int)pos[prime[x]].size() == 0) {
    303             L[l] = 0;
    304             return;
    305         }
    306         L[l] = min(L[l], pos[prime[x]].back());
    307         pos[prime[x]].pop_back();
    308         x /= prime[x];
    309     }
    310 }
    311 
    312 int main() {
    313     ios_base::sync_with_stdio(0);
    314     cin.tie(0);
    315     cout.tie(0);
    316 
    317     int n;
    318     cin >> n;
    319     for (int i = 1; i <= n; ++i) cin >> a[i];
    320 
    321     for (int i = 2; i < maxn; ++i) {
    322         if (prime[i] == 0) {
    323             prime[i] = i;
    324             if (i > 1000) continue;
    325             for (int j = i * i; j < maxn; j += i) {
    326                 prime[j] = i;
    327             }
    328         }
    329     }
    330 
    331     char type;
    332     for (int i = 1; i <= n; ++i) {
    333         cin >> type;
    334         if (type == '*') add(a[i], i);
    335         else del(a[i], i);
    336     }
    337 
    338     ll answer = 0;
    339     vector < pair < int, int > > f_min;
    340     for (int i = n; i >= 1; --i) {
    341         int cnt = 1;
    342         while ((int)f_min.size() > 0 && f_min.back().first >= L[i]) {
    343             cnt += f_min.back().second;
    344             f_min.pop_back();
    345         }
    346         f_min.push_back({L[i], cnt});
    347         if (L[i] == i) answer += (ll)cnt;
    348     }
    349     cout << answer << '\n';
    350     return 0;
    351 }
    352 ```