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 ```