codeforces-scrape

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

1618.md (9855B)


      1 Source: https://codeforces.com/blog/entry/97927
      2 
      3 [1618A - Polycarp and Sums of Subsequences](/contest/1618/problem/A "Codeforces Round 760 (Div. 3)")
      4 
      5 Idea: [Brovko](/profile/Brovko "International Master Brovko"), preparation: [Brovko](/profile/Brovko "International Master Brovko")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Brovko)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main()
     19 {
     20     ios_base::sync_with_stdio(0);
     21     cin.tie(0);
     22     cout.tie(0);
     23     int t;
     24     cin >> t;
     25     for(int i = 0; i < t; i++)
     26     {
     27         vector <int> b(7);
     28 
     29         for(int i = 0; i < 7; i++)
     30             cin >> b[i];
     31 
     32         cout << b[0] << ' ' << b[1] << ' ' << b[6] - b[0] - b[1] << endl;
     33     }
     34 }
     35 ```
     36 
     37 [1618B - Missing Bigram](/contest/1618/problem/B "Codeforces Round 760 (Div. 3)")
     38 
     39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (awoo)**
     46 
     47 ```
     48 for _ in range(int(input())):
     49 	n = int(input())
     50 	s = input().split()
     51 	for i in range(n - 3):
     52 		if s[i][1] != s[i + 1][0]:
     53 			s.insert(i + 1, s[i][1] + s[i + 1][0])
     54 			break
     55 	else:
     56 		s.append(s[-1][1] + 'a')
     57 	print(s[0][0], end="")
     58 	for i in range(n - 1):
     59 		print(s[i][1], end="")
     60 	print()
     61 ```
     62 
     63 [1618C - Paint the Array](/contest/1618/problem/C "Codeforces Round 760 (Div. 3)")
     64 
     65 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution (BledDest)**
     72 
     73 ```
     74 #include <bits/stdc++.h>     
     75 
     76 using namespace std;
     77 
     78 void solve()
     79 {
     80     int n;
     81     cin >> n;
     82     vector<long long> a(n);
     83     for(int i = 0; i < n; i++)
     84     {
     85         cin >> a[i];
     86     }
     87     vector<long long> g(a.begin(), a.begin() + 2);
     88     for(int i = 0; i < n; i++)
     89     {
     90         g[i % 2] = __gcd(g[i % 2], a[i]);
     91     }  
     92     vector<bool> good(2, true);
     93     for(int i = 0; i < n; i++)
     94     {
     95         good[i % 2] = good[i % 2] && (a[i] % g[(i % 2) ^ 1] > 0);
     96     }   
     97     long long ans = 0;
     98     for(int i = 0; i < 2; i++)
     99         if(good[i])
    100             ans = max(ans, g[i ^ 1]);
    101     cout << ans << endl;
    102 }
    103 
    104 int main()
    105 {
    106     int t;
    107     cin >> t;
    108     for(int i = 0; i < t; i++)
    109     {
    110         solve();
    111     }
    112 }
    113 ```
    114 
    115 [1618D - Array and Operations](/contest/1618/problem/D "Codeforces Round 760 (Div. 3)")
    116 
    117 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution (BledDest)**
    124 
    125 ```
    126 def solve():
    127     n, k = map(int, input().split())
    128     a = list(map(int, input().split()))
    129 
    130     a = sorted(a)
    131     cost = sum(a[0:n-2*k]) + sum(map(lambda x: a[x+n-2*k] // a[x+n-k], range(0, k)))
    132     print(cost)
    133     
    134 t = int(input())
    135 for i in range(t):
    136     solve()
    137 ```
    138 
    139 [1618E - Singers' Tour](/contest/1618/problem/E "Codeforces Round 760 (Div. 3)")
    140 
    141 Idea: [shnirelman](/profile/shnirelman "Master shnirelman"), preparation: [shnirelman](/profile/shnirelman "Master shnirelman")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution (shnirelman)**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151 
    152 using namespace std;
    153 using li = long long;
    154 
    155 const int N = 50013;
    156 
    157 int b[N];
    158 int a[N];
    159 
    160 void solve() {
    161     
    162     int n;
    163     cin >> n;
    164 
    165     li sumb = 0;
    166     for(int i = 0; i < n; i++) {
    167         cin >> b[i];
    168         sumb += b[i];
    169     }
    170 
    171     li d = n * 1ll * (n + 1) / 2;
    172 
    173     if(sumb % d != 0) {
    174         cout << "NO" << endl;
    175         return;
    176     }
    177 
    178     li suma = sumb / d;
    179 
    180     for(int i = n - 1; i >= 0; i--) {
    181         li res = (b[i] - b[(i + 1) % n] + suma);
    182         if(res % n != 0 || res <= 0) {
    183             cout << "NO" << endl;
    184             return;
    185         }
    186 
    187         a[(i + 1) % n] = res / n;
    188     }
    189 
    190     cout << "YES" << endl;
    191     for(int i = 0; i < n; i++)
    192         cout << a[i] << ' ';
    193     cout << endl;
    194 }
    195 
    196 int main()
    197 {
    198     ios::sync_with_stdio(0);
    199     cin.tie(0);
    200 
    201     int t;
    202     cin >> t;
    203     for(int i = 0; i < t; i++)
    204         solve();
    205 }
    206 ```
    207 
    208 [1618F - Reverse](/contest/1618/problem/F "Codeforces Round 760 (Div. 3)")
    209 
    210 Idea: [Lankin](/profile/Lankin "Expert Lankin"), preparation: [Lankin](/profile/Lankin "Expert Lankin")
    211 
    212 **Tutorial**
    213 
    214 Tutorial is loading...
    215 
    216 **Solution (awoo)**
    217 
    218 ```
    219 a, b = map(int, input().split())
    220 s = bin(b)[2:]
    221 t = bin(a)[2:]
    222 if s == t:
    223     print("YES")
    224     exit(0)
    225 for q in [t + '1', t.strip('0')]:
    226     for l in range(len(s) - len(q) + 1):
    227         r = len(s) - len(q) - l
    228         if '1' * l + q + '1' * r == s or '1' * l + q[::-1] + '1' * r == s:
    229             print("YES")
    230             exit(0)
    231 print("NO")
    232 ```
    233 
    234 **Solution (BledDest)**
    235 
    236 ```
    237 #include<bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 string go(string t)
    242 {
    243     while(t.back() == '0') t.pop_back();
    244     reverse(t.begin(), t.end());
    245     return t;
    246 }
    247 
    248 string to_bin(long long x)
    249 {
    250     if(x == 0)
    251         return "";
    252     else
    253     {
    254         string s = to_bin(x / 2);
    255         s.push_back(char('0' + x % 2));
    256         return s;
    257     }
    258 }
    259 
    260 int main()
    261 {
    262     long long x, y;
    263     cin >> x >> y;
    264     set<string> used;
    265     queue<string> q;
    266     q.push(to_bin(x));
    267     used.insert(to_bin(x));
    268     while(!q.empty())
    269     {
    270         string k = q.front();
    271         q.pop();
    272         if(k.size() > 100) continue;
    273         for(int i = 0; i < 2; i++)
    274         {
    275             string k2 = go(k + string(1, char('0' + i)));
    276             if(!used.count(k2))
    277             {
    278                 used.insert(k2);
    279                 q.push(k2);
    280             }
    281         }
    282     }
    283     if(used.count(to_bin(y)))
    284         cout << "YES\n";
    285     else
    286         cout << "NO\n";
    287 }
    288 ```
    289 
    290 [1618G - Trader Problem](/contest/1618/problem/G "Codeforces Round 760 (Div. 3)")
    291 
    292 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    293 
    294 **Tutorial**
    295 
    296 Tutorial is loading...
    297 
    298 **Solution (awoo)**
    299 
    300 ```
    301 #include <bits/stdc++.h>
    302 
    303 using namespace std;
    304 
    305 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    306 
    307 const int N = 400 * 1000 + 13;
    308 
    309 int n, m, k;
    310 int a[N], b[N];
    311 int q[N];
    312 
    313 int p[N];
    314 multiset<int> wst[N], bst[N];
    315 long long sum;
    316 
    317 int getp(int a){
    318 	return a == p[a] ? a : p[a] = getp(p[a]);
    319 }
    320 
    321 void unite(int a, int b){
    322 	a = getp(a), b = getp(b);
    323 	if (wst[a].size() + bst[a].size() < wst[b].size() + bst[b].size()) swap(a, b);
    324 	for (auto it : wst[b])
    325 		wst[a].insert(it);
    326 	for (auto it : bst[b])
    327 		bst[a].insert(it);
    328 	wst[b].clear();
    329 	bst[b].clear();
    330 	while (!bst[a].empty() && !wst[a].empty() && *bst[a].begin() < *wst[a].rbegin()){
    331 		sum -= *bst[a].begin();
    332 		sum += *wst[a].rbegin();
    333 		bst[a].insert(*wst[a].rbegin());
    334 		wst[a].insert(*bst[a].begin());
    335 		bst[a].erase(bst[a].begin());
    336 		wst[a].erase(--wst[a].end());
    337 	}
    338 	p[b] = a;
    339 }
    340 
    341 long long ans[N];
    342 
    343 struct event{
    344 	int x, t, i;
    345 };
    346 
    347 int main() {
    348 	scanf("%d%d%d", &n, &m, &k);
    349 	forn(i, n)
    350 		scanf("%d", &a[i]);
    351 	forn(i, m)
    352 		scanf("%d", &b[i]);
    353 	forn(i, k)
    354 		scanf("%d", &q[i]);
    355 	vector<pair<int, int>> tot;
    356 	forn(i, n) tot.push_back({a[i], 1});
    357 	forn(i, m) tot.push_back({b[i], 0});
    358 	sort(tot.begin(), tot.end());
    359 	sum = accumulate(a, a + n, 0ll);
    360 	forn(i, n + m){
    361 		p[i] = i;
    362 		wst[i].clear();
    363 		bst[i].clear();
    364 		if (tot[i].second) bst[i].insert(tot[i].first);
    365 		else wst[i].insert(tot[i].first);
    366 	}
    367 	vector<event> ev;
    368 	forn(i, n + m - 1) ev.push_back({tot[i + 1].first - tot[i].first, 0, i});
    369 	forn(i, k) ev.push_back({q[i], 1, i});
    370 	sort(ev.begin(), ev.end(), [](const event &a, const event &b){
    371 		if (a.x != b.x) return a.x < b.x;
    372 		return a.t < b.t;
    373 	});
    374 	for (auto it : ev){
    375 		if (it.t == 0)
    376 			unite(it.i, it.i + 1);
    377 		else
    378 			ans[it.i] = sum;
    379 	}
    380 	forn(i, k) printf("%lld\n", ans[i]);
    381 }
    382 ```
    383 
    384 **Solution (BledDest)**
    385 
    386 ```
    387 #include<bits/stdc++.h>
    388 
    389 using namespace std;
    390 
    391 long long get(const vector<int>& pcnt, const vector<long long>& psum, pair<int, int> seg)
    392 {
    393     int L = seg.first;
    394     int R = seg.second;
    395     int cnt = pcnt[R] - pcnt[L];
    396     return psum[R] - psum[R - cnt];
    397 }
    398 
    399 int main()
    400 {
    401     int n, m, q;
    402     scanf("%d %d %d", &n, &m, &q);
    403     vector<int> a(n), b(m);
    404     for(int i = 0; i < n; i++)
    405     {
    406         scanf("%d", &a[i]);
    407     }
    408     for(int i = 0; i < m; i++)
    409     {
    410         scanf("%d", &b[i]);
    411     }
    412     vector<int> pcnt = {0};
    413     vector<long long> psum = {0ll};
    414     vector<pair<int, int>> order;
    415     for(int i = 0; i < n; i++) order.push_back(make_pair(a[i], 1));
    416     for(int i = 0; i < m; i++) order.push_back(make_pair(b[i], 0));
    417     sort(order.begin(), order.end());
    418     int z = n + m;
    419     for(int i = 0; i < z; i++)
    420     {
    421         pcnt.push_back(pcnt.back() + order[i].second);
    422         psum.push_back(psum.back() + order[i].first);
    423     }
    424     long long cur = 0;
    425     for(int i = 0; i < n; i++)
    426         cur += a[i];
    427     set<pair<int, int>> segs;
    428     for(int i = 0; i < z; i++)
    429         segs.insert(make_pair(i, i + 1));
    430     map<int, vector<int>> events;
    431     for(int i = 0; i < z - 1; i++)
    432         events[order[i + 1].first - order[i].first].push_back(i);
    433     vector<pair<int, long long>> ans = {{0, cur}};
    434     for(auto x : events)
    435     {
    436         int cost = x.first;
    437         vector<int> changes = x.second;
    438         for(auto i : changes)
    439         {
    440             auto itr = segs.upper_bound(make_pair(i, int(1e9)));
    441             auto itl = prev(itr);
    442             pair<int, int> pl = *itl;
    443             pair<int, int> pr = *itr;
    444             cur -= get(pcnt, psum, pl);
    445             cur -= get(pcnt, psum, pr);
    446             pair<int, int> p = make_pair(pl.first, pr.second);
    447             cur += get(pcnt, psum, p);
    448             segs.erase(pl);
    449             segs.erase(pr);
    450             segs.insert(p);
    451         }
    452         ans.push_back(make_pair(cost, cur));
    453     }              
    454     for(int i = 0; i < q; i++)
    455     {
    456         int k;
    457         scanf("%d", &k);
    458         int pos = upper_bound(ans.begin(), ans.end(), make_pair(k + 1, -1ll)) - ans.begin() - 1;
    459         printf("%lld\n", ans[pos].second);
    460     }
    461 }
    462 ```