codeforces-scrape

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

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 &mdash; a1 * (k1 &mdash; 1) &mdash; a2 * (k2 &mdash; 1));
     28 	int maxCnt = 0;
     29 	if (n <= a1 * k1) {
     30 		maxCnt = n / k1;
     31 	} else {
     32 		maxCnt = a1 + (n &mdash; 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 ```