1215.md (8267B)
1 Source: https://codeforces.com/blog/entry/69815 2 3 [1215A - Yellow Cards](/contest/1215/problem/A "Codeforces Round 585 (Div. 2)") 4 5 **Editorial** 6 7 Tutorial is loading... 8 9 **Solution (fcspartakm)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int a1, a2, k1, k2, n; 17 18 inline void read() { 19 cin >> a1 >> a2 >> k1 >> k2 >> n; 20 } 21 22 inline void solve() { 23 if (k1 > k2) { 24 swap(k1, k2); 25 swap(a1, a2); 26 } 27 int minCnt = max(0, n — a1 * (k1 — 1) — a2 * (k2 — 1)); 28 int maxCnt = 0; 29 if (n <= a1 * k1) { 30 maxCnt = n / k1; 31 } else { 32 maxCnt = a1 + (n — a1 * k1) / k2; 33 } 34 cout << minCnt << ' ' << maxCnt << endl; 35 } 36 37 int main () { 38 #ifdef fcspartakm 39 freopen("input.txt", "r", stdin); 40 //freopen("output.txt", "w", stdout); 41 #endif 42 srand(time(NULL)); 43 cerr << setprecision(10) << fixed; 44 45 read(); 46 solve(); 47 48 //cerr << "TIME: " << clock() << endl; 49 } 50 ``` 51 52 [1215B - The Number of Products](/contest/1215/problem/B "Codeforces Round 585 (Div. 2)") 53 54 **Editorial** 55 56 Tutorial is loading... 57 58 **Solution (fcspartakm)** 59 60 ``` 61 #include <bits/stdc++.h> 62 63 using namespace std; 64 65 const int N = 200 * 1000 + 13; 66 67 int n; 68 int a[N]; 69 70 inline void read() { 71 cin >> n; 72 for (int i = 0; i < n; i++) { 73 cin >> a[i]; 74 } 75 } 76 77 inline void solve() { 78 int pos = -1; 79 li ans0 = 0; 80 for (int i = 0; i < n; i++) { 81 if (a[i] == 0) { 82 pos = i; 83 } 84 if (pos != -1) { 85 ans0 += pos + 1; 86 } 87 } 88 int cnt1 = 0, cnt2 = 0; 89 int bal = 0; 90 li ansP = 0; 91 for (int i = 0; i < n; i++) { 92 if (a[i] == 0) { 93 cnt1 = 0, cnt2 = 0, bal = 0; 94 continue; 95 } 96 if (bal % 2 == 0) { 97 cnt1++; 98 } else { 99 cnt2++; 100 } 101 if (a[i] < 0) { 102 bal++; 103 } 104 if (bal % 2 == 0) { 105 ansP += cnt1; 106 } else { 107 ansP += cnt2; 108 } 109 } 110 cout << n * 1ll * (n + 1) / 2 - ans0 - ansP << ' ' << ansP << endl; 111 } 112 113 int main () { 114 #ifdef fcspartakm 115 freopen("input.txt", "r", stdin); 116 //freopen("output.txt", "w", stdout); 117 #endif 118 srand(time(NULL)); 119 cerr << setprecision(10) << fixed; 120 121 read(); 122 solve(); 123 124 //cerr << "TIME: " << clock() << endl; 125 } 126 ``` 127 128 [1215C - Swap Letters](/contest/1215/problem/C "Codeforces Round 585 (Div. 2)") 129 130 **Editorial** 131 132 Tutorial is loading... 133 134 **Solution (fcspartakm)** 135 136 ``` 137 #include<bits/stdc++.h> 138 139 using namespace std; 140 141 int n; 142 string s, t; 143 144 inline void read() { 145 cin >> n >> s >> t; 146 } 147 148 inline void solve() { 149 vector<int> pos01, pos10; 150 for (int i = 0; i < n; i++) { 151 if (s[i] != t[i]) { 152 if (s[i] == 'a') { 153 pos01.pb(i); 154 } else { 155 pos10.pb(i); 156 } 157 } 158 } 159 if (sz(pos01) % 2 != sz(pos10) % 2) { 160 cout << -1 << endl; 161 return; 162 } 163 vector<pair<int, int> > ans; 164 for (int i = 0; i + 1 < sz(pos01); i += 2) { 165 ans.pb(mp(pos01[i], pos01[i + 1])); 166 } 167 for (int i = 0; i + 1 < sz(pos10); i += 2) { 168 ans.pb(mp(pos10[i], pos10[i + 1])); 169 } 170 if (sz(pos01) % 2) { 171 int x = pos01.back(); 172 int y = pos10.back(); 173 ans.pb(mp(x, x)); 174 ans.pb(mp(x, y)); 175 } 176 cout << sz(ans) << endl; 177 for (int i = 0; i < sz(ans); i++) { 178 cout << ans[i].ft + 1 << ' ' << ans[i].sc + 1 << endl; 179 } 180 } 181 182 int main () { 183 #ifdef fcspartakm 184 freopen("input.txt", "r", stdin); 185 //freopen("output.txt", "w", stdout); 186 #endif 187 srand(time(NULL)); 188 cerr << setprecision(10) << fixed; 189 190 read(); 191 solve(); 192 193 //cerr << "TIME: " << clock() << endl; 194 } 195 ``` 196 197 [1215D - Ticket Game](/contest/1215/problem/D "Codeforces Round 585 (Div. 2)") 198 199 **Editorial** 200 201 Tutorial is loading... 202 203 **Solution (fcspartakm)** 204 205 ``` 206 #include <iostream> 207 #include <set> 208 #include <string> 209 #include <vector> 210 #include <algorithm> 211 #include <cmath> 212 213 using namespace std; 214 215 int n; 216 217 int main() { 218 cin >> n; 219 long double sum1 = 0, sum2 = 0; 220 string s; 221 cin >> s; 222 for (int i = 0; i < n; i++) { 223 if (s[i] != '?') { 224 if (i < n / 2) { 225 sum1 += (long double)(s[i] - '0'); 226 } else { 227 sum2 += (long double)(s[i] - '0'); 228 } 229 } else { 230 if (i < n / 2) { 231 sum1 += (long double)4.5; 232 } else { 233 sum2 += (long double)4.5; 234 } 235 } 236 } 237 if (fabsl(sum1 - sum2) < 1e-9) { 238 cout << "Bicarp" << endl; 239 } else { 240 cout << "Monocarp" << endl; 241 } 242 } 243 ``` 244 245 [1215E - Marbles](/contest/1215/problem/E "Codeforces Round 585 (Div. 2)") 246 247 **Editorial** 248 249 Tutorial is loading... 250 251 **Solution (fcspartakm)** 252 253 ``` 254 #include <iostream> 255 #include <set> 256 #include <string> 257 #include <vector> 258 #include <algorithm> 259 260 using namespace std; 261 262 const int N = 1000 * 1000 + 13; 263 const int M = 20 + 1; 264 const long long INF = 1000 * 1000 * 1000 * 1ll * 1000 * 1000 * 1000; 265 266 int n; 267 long long d[(1 << M)]; 268 long long cnt[M][M]; 269 vector<int> col[M]; 270 271 int main() { 272 cin >> n; 273 for (int i = 0; i < n; i++) { 274 int x; 275 cin >> x; 276 x--; 277 col[x].push_back(i); 278 } 279 for (int i = 0; i < 20; i++) { 280 for (int j = 0; j < 20; j++) { 281 if (i == j) { 282 continue; 283 } 284 if ((int)col[i].size() == 0 || (int)col[j].size() == 0) { 285 continue; 286 } 287 int pos2 = 0; 288 for (int pos1 = 0; pos1 < (int)col[i].size(); pos1++) { 289 while (true) { 290 if (pos2 == (int)col[j].size() - 1 || col[j][pos2 + 1] > col[i][pos1]) { 291 break; 292 } 293 pos2++; 294 } 295 if (col[i][pos1] > col[j][pos2]) { 296 cnt[i][j] += pos2 + 1; 297 } 298 } 299 } 300 } 301 302 for (int mask = 0; mask < (1 << 20); mask++) { 303 d[mask] = INF; 304 } 305 d[0] = 0; 306 for (int mask = 0; mask < (1 << 20); mask++) { 307 vector<int> was; 308 for (int i = 0; i < 20; i++) { 309 if (mask & (1 << i)) { 310 was.push_back(i); 311 } 312 } 313 for (int i = 0; i < 20; i++) { 314 if (mask & (1 << i)) { 315 continue; 316 } 317 long long sum = 0; 318 for (int j = 0; j < (int)was.size(); j++) { 319 sum += cnt[was[j]][i]; 320 } 321 int nmask = mask | (1 << i); 322 d[nmask] = min(d[nmask], d[mask] + sum); 323 } 324 } 325 cout << d[(1 << 20) - 1] << endl; 326 } 327 ``` 328 329 [1215F - Radio Stations](/contest/1215/problem/F "Codeforces Round 585 (Div. 2)") 330 331 **Editorial** 332 333 Tutorial is loading... 334 335 **Solution (BledDest)** 336 337 ``` 338 #include<bits/stdc++.h> 339 340 using namespace std; 341 342 const int N = 1600043; 343 344 vector<int> g[N]; 345 vector<int> gt[N]; 346 int used[N]; 347 vector<int> order; 348 int comp[N]; 349 vector<int> result; 350 int v; 351 352 void add_edge(int v1, int v2) 353 { 354 g[v1].push_back(v2); 355 gt[v2].push_back(v1); 356 } 357 358 void add_disjunction(int v1, int v2) 359 { 360 add_edge(v1 ^ 1, v2); 361 add_edge(v2 ^ 1, v1); 362 } 363 364 void dfs1(int v) 365 { 366 if(used[v]) return; 367 used[v] = 1; 368 for(auto u : g[v]) 369 dfs1(u); 370 order.push_back(v); 371 } 372 373 void dfs2(int v, int cc) 374 { 375 if(comp[v]) return; 376 comp[v] = cc; 377 for(auto u : gt[v]) 378 dfs2(u, cc); 379 } 380 381 bool solve2SAT() 382 { 383 for(int i = 0; i < v * 2; i++) 384 dfs1(i); 385 reverse(order.begin(), order.end()); 386 int cc = 0; 387 for(auto x : order) 388 { 389 if(comp[x] == 0) 390 { 391 cc++; 392 dfs2(x, cc); 393 } 394 } 395 for(int i = 0; i < v; i++) 396 { 397 if(comp[i * 2] == comp[i * 2 + 1]) 398 return false; 399 else if(comp[i * 2] > comp[i * 2 + 1]) 400 result.push_back(i); 401 } 402 return true; 403 } 404 405 int main() 406 { 407 int n, p, M, m; 408 scanf("%d %d %d %d", &n, &p, &M, &m); 409 v = p + M - 1; 410 for(int i = 0; i < n; i++) 411 { 412 int x, y; 413 scanf("%d %d", &x, &y); 414 --x; 415 --y; 416 add_disjunction(x * 2, y * 2); 417 } 418 for(int i = 0; i < p; i++) 419 { 420 int l, r; 421 scanf("%d %d", &l, &r); 422 if(l != 1) 423 add_disjunction((l - 2 + p) * 2, i * 2 + 1); 424 if(r != M) 425 add_disjunction((r - 1 + p) * 2 + 1, i * 2 + 1); 426 } 427 for(int i = 0; i < m; i++) 428 { 429 int x, y; 430 scanf("%d %d", &x, &y); 431 --x; 432 --y; 433 add_disjunction(x * 2 + 1, y * 2 + 1); 434 } 435 for(int i = 2; i <= M - 1; i++) 436 { 437 int f1 = i - 2 + p; 438 int f2 = f1 + 1; 439 add_disjunction(f1 * 2, f2 * 2 + 1); 440 } 441 if(!solve2SAT()) 442 { 443 puts("-1"); 444 return 0; 445 } 446 int k = 1; 447 vector<int> stations; 448 for(auto x : result) 449 if(x < p) 450 stations.push_back(x); 451 else 452 k = max(k, x - p + 2); 453 printf("%d %d\n", int(stations.size()), k); 454 for(auto x : stations) 455 printf("%d ", x + 1); 456 return 0; 457 } 458 ```