codeforces-scrape

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

985.md (10460B)


      1 Source: https://codeforces.com/blog/entry/59623
      2 
      3 [985A - Chess Placing](/contest/985/problem/A "Educational Codeforces Round 44 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 	int n;
     18 	cin >> n;
     19 	vector<int> pos(n / 2);
     20 	for (int i = 0; i < n / 2; ++i)
     21 		cin >> pos[i];
     22 	sort(pos.begin(), pos.end());
     23 	
     24 	int ans1 = 0, ans2 = 0;
     25 	for (int i = 0; i < n / 2; ++i) {
     26 		ans1 += abs(pos[i] - (i * 2 + 1));
     27 		ans2 += abs(pos[i] - (i * 2 + 2));
     28 	}
     29 	
     30 	cout << min(ans1, ans2) << endl;
     31 	
     32 	return 0;
     33 }
     34 ```
     35 
     36 [985B - Switches and Lamps](/contest/985/problem/B "Educational Codeforces Round 44 (Rated for Div. 2)")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Solution (Vovuh)**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50 	int n, m;
     51 	cin >> n >> m;
     52 	vector<string> s(n);
     53 	vector<int> cnt(m);
     54 	for (int i = 0; i < n; ++i) {
     55 		cin >> s[i];
     56 		for (int j = 0; j < m; ++j)
     57 			if (s[i][j] == '1') ++cnt[j];
     58 	}
     59 	
     60 	for (int i = 0; i < n; ++i) {
     61 		bool ok = true;
     62 		for (int j = 0; j < m; ++j) {
     63 			if (s[i][j] == '1' && cnt[j] == 1)
     64 				ok = false;
     65 		}
     66 		if (ok) {
     67 			puts("YES");
     68 			return 0;
     69 		}
     70 	}
     71 	
     72 	puts("NO");
     73 	
     74 	return 0;
     75 }
     76 ```
     77 
     78 [985C - Liebig's Barrels](/contest/985/problem/C "Educational Codeforces Round 44 (Rated for Div. 2)")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution (adedalic)**
     85 
     86 ```
     87 #include<bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     92 
     93 typedef long long li;
     94 
     95 int n, k, l, m;
     96 vector<li> a;
     97 
     98 inline bool read() {
     99 	if(!(cin >> n >> k >> l))
    100 		return false;
    101 	m = n * k;
    102 	a.assign(m, 0);
    103 	fore(i, 0, m)
    104 		assert(scanf("%lld", &a[i]) == 1);
    105 	return true;
    106 }
    107 
    108 inline void solve() {
    109 	sort(a.begin(), a.end());
    110 	int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
    111 	
    112 	if(rg < n) {
    113 		puts("0");
    114 		return;
    115 	}
    116 	li ans = 0;
    117 	
    118 	int u = 0;
    119 	fore(i, 0, n) {
    120 		ans += a[u++];
    121 		
    122 		fore(j, 0, k - 1) {
    123 			if(rg - u > n - i - 1)
    124 				u++;
    125 			else
    126 				break;
    127 		}
    128 	}
    129 	cout << ans << endl;
    130 }
    131 
    132 int main() {
    133 #ifdef _DEBUG
    134 	freopen("input.txt", "r", stdin);
    135 	int tt = clock();
    136 #endif
    137 	cerr << fixed << setprecision(15);
    138 	
    139 	if(read()) {
    140 		solve();
    141 	
    142 #ifdef _DEBUG
    143 		cerr << "TIME = " << clock() - tt << endl;
    144 		tt = clock();
    145 #endif
    146 	}
    147 	return 0;
    148 }
    149 ```
    150 
    151 [985D - Sand Fortress](/contest/985/problem/D "Educational Codeforces Round 44 (Rated for Div. 2)")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution (PikMike)**
    158 
    159 ```
    160 #include <bits/stdc++.h>
    161 
    162 #define forn(i, n) for (int i = 0; i < int(n); i++)
    163 
    164 typedef long long li;
    165 
    166 using namespace std;
    167 
    168 const int INF = 2e9;
    169 li n, h;
    170 
    171 bool check(li maxh){
    172 	li k = min(h, maxh);
    173 	li cnt = maxh * maxh - k * (k - 1) / 2;
    174 	return (cnt <= n);
    175 }
    176 
    177 li get(li maxh){
    178 	li k = min(h, maxh);
    179 	li cnt = maxh * maxh - k * (k - 1) / 2;
    180 	li len = (2 * maxh - 1) - (k - 1);
    181 	n -= cnt;
    182 	return len + (n + maxh - 1) / maxh;
    183 }
    184 
    185 int main() {
    186 	scanf("%lld%lld", &n, &h);
    187 	li l = 1, r = INF;
    188 	
    189 	while (l < r - 1){
    190 		li m = (l + r) / 2;
    191 		
    192 		if (check(m))
    193 			l = m;
    194 		else
    195 			r = m;
    196 	}
    197 	
    198 	printf("%lld\n", check(r) ? get(r) : get(l));
    199 	return 0;
    200 }
    201 ```
    202 
    203 [985E - Pencils and Boxes](/contest/985/problem/E "Educational Codeforces Round 44 (Rated for Div. 2)")
    204 
    205 **Tutorial**
    206 
    207 Tutorial is loading...
    208 
    209 **Solution (PikMike)**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213  
    214 using namespace std;
    215  
    216 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    217 
    218 const int N = 500 * 1000 + 13;
    219 
    220 int f[N];
    221 
    222 void upd(int x){
    223     for (int i = x; i < N; i |= i + 1)
    224         ++f[i];
    225 }
    226 
    227 int sum(int x){
    228     int res = 0;
    229     for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    230         res += f[i];
    231     return res;
    232 }
    233 
    234 int get(int l, int r){
    235 	if (l > r) return 0;
    236 	return sum(r) - sum(l - 1);
    237 }
    238 
    239 int main(){
    240 	int n, k, dif;
    241 	scanf("%d%d%d", &n, &k, &dif);
    242 	vector<int> a(n);
    243 	forn(i, n)
    244 		scanf("%d", &a[i]);
    245 	sort(a.begin(), a.end());
    246 	
    247 	vector<int> dp(n + 1, 0);
    248 	
    249 	dp[0] = 1;
    250 	upd(0);
    251 	
    252 	int l = 0;
    253 	forn(i, n){
    254 		while (l < i && a[i] - a[l] > dif)
    255 			++l;
    256 		dp[i + 1] = (get(l, i - k + 1) >= 1);
    257 		if (dp[i + 1]) upd(i + 1);
    258 	}
    259 	
    260 	puts(dp[n] ? "YES" : "NO");
    261 }
    262 ```
    263 
    264 [985F - Isomorphic Strings](/contest/985/problem/F "Educational Codeforces Round 44 (Rated for Div. 2)")
    265 
    266 **Tutorial**
    267 
    268 Tutorial is loading...
    269 
    270 **Solution (adedalic)**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 
    275 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    276 #define sz(a) int(a.size())
    277 
    278 #define x first
    279 #define y second
    280 
    281 using namespace std;
    282 
    283 const int B = 2;
    284 
    285 typedef array<int, B> ht;
    286 
    287 ht MOD, BASE;
    288 
    289 inline int norm(int a, const int &MOD) {
    290 	while(a >= MOD)
    291 		a -= MOD;
    292 	while(a < 0)
    293 		a += MOD;
    294 	return a;
    295 }
    296 
    297 inline int mul(int a, int b, const int &MOD) {
    298 	return int(a * 1ll * b % MOD);
    299 }
    300 
    301 inline ht operator +(const ht &a, const ht &b) {
    302 	ht ans;
    303 	fore(i, 0, sz(ans))
    304 		ans[i] = norm(a[i] + b[i], MOD[i]);
    305 	return ans;
    306 }
    307 
    308 inline ht operator -(const ht &a, const ht &b) {
    309 	ht ans;
    310 	fore(i, 0, sz(ans))
    311 		ans[i] = norm(a[i] - b[i], MOD[i]);
    312 	return ans;
    313 }
    314 
    315 inline ht operator *(const ht &a, const ht &b) {
    316 	ht ans;
    317 	fore(i, 0, sz(ans))
    318 		ans[i] = mul(a[i], b[i], MOD[i]);
    319 	return ans;
    320 }
    321 
    322 int CMODS[] = {int(1e9) + 7, int(1e9) + 9, int(1e9) + 21, int(1e9) + 33, int(1e9) + 87, int(1e9) + 93, int(1e9) + 97, int(1e9) + 103};
    323 int CBASE[] = {1009, 1013, 1019, 1021};
    324 
    325 const int N = 200 * 1000 + 555;
    326 
    327 int n, m;
    328 char s[N];
    329 int x[N], y[N], len[N];
    330 
    331 inline bool read() {
    332 	if(!(cin >> n >> m))
    333 		return false;
    334 	assert(scanf("%s", s) == 1);
    335 	
    336 	fore(i, 0, m) {
    337 		assert(scanf("%d%d%d", &x[i], &y[i], &len[i]) == 3);
    338 		x[i]--, y[i]--;
    339 	}
    340 	return true;
    341 }
    342 void setMods() {
    343 	mt19937 rnd;
    344 	unsigned int seed = n;
    345 	fore(i, 0, n)
    346 		seed = (seed * 3) + s[i];
    347 	fore(i, 0, m) {
    348 		seed = (seed * 3) + x[i];
    349 		seed = (seed * 3) + y[i];
    350 		seed = (seed * 3) + len[i];
    351 	}
    352 	rnd.seed(seed);
    353 	
    354 	set<int> mids;
    355 	while(sz(mids) < sz(MOD))
    356 		mids.insert(rnd() % 8);
    357 	vector<int> vmids(mids.begin(), mids.end());
    358 	fore(i, 0, sz(MOD)) {
    359 		MOD[i] = CMODS[vmids[i]];
    360 		BASE[i] = CBASE[i];
    361 	}
    362 }
    363 
    364 ht pBase[N];
    365 ht ph[27][N];
    366 vector<int> ord[N];
    367 
    368 ht getHash(int id, int l, int r) {
    369 	return ph[id][r] - ph[id][l] * pBase[r - l];
    370 }
    371 
    372 inline void solve() {
    373 	setMods();
    374 	
    375 	pBase[0] = {1, 1};
    376 	fore(i, 1, N)
    377 		pBase[i] = pBase[i - 1] * BASE;
    378 		
    379 	fore(c, 0, 26) {
    380 		ph[c][0] = {0, 0};
    381 		fore(i, 0, n) {
    382 			int val = (s[i] == c + 'a');
    383 			ph[c][i + 1] = ph[c][i] * BASE + ht{val, val};
    384 		}
    385 	}
    386 	
    387 	vector<int> curOrd(26, 0);
    388 	iota(curOrd.begin(), curOrd.end(), 0);
    389 	for(int i = n - 1; i >= 0; i--) {
    390 		ord[i] = curOrd;
    391 		auto it = find(ord[i].begin(), ord[i].end(), int(s[i] - 'a'));
    392 		ord[i].erase(it);
    393 		ord[i].insert(ord[i].begin(), int(s[i] - 'a'));
    394 		curOrd = ord[i];
    395 	}
    396 	
    397 	fore(q, 0, m) {
    398 		int s1 = x[q], s2 = y[q];
    399 		bool ok = true;
    400 		
    401 		fore(i, 0, 26) {
    402 			if(getHash(ord[s1][i], s1, s1 + len[q]) != 
    403 				getHash(ord[s2][i], s2, s2 + len[q])) {
    404 				ok = false;
    405 				break;
    406 			}
    407 		}
    408 		puts(ok ? "YES" : "NO");
    409 	}
    410 }
    411 
    412 int main(){
    413 #ifdef _DEBUG
    414 	freopen("input.txt", "r", stdin);
    415 	//freopen("output.txt", "w", stdout);
    416 #endif
    417 	if(read()) {
    418 		solve();
    419 	}
    420 	return 0;
    421 }
    422 ```
    423 
    424 [985G - Team Players](/contest/985/problem/G "Educational Codeforces Round 44 (Rated for Div. 2)")
    425 
    426 **Tutorial**
    427 
    428 Tutorial is loading...
    429 
    430 **Solution (adedalic)**
    431 
    432 ```
    433 #include <bits/stdc++.h>
    434 
    435 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    436 #define sz(a) int(a.size())
    437 
    438 using namespace std;
    439 
    440 typedef unsigned long long uli;
    441 
    442 const int N = 200 * 1000 + 555;
    443 
    444 int n, m;
    445 uli a, b, c;
    446 vector<int> g[N];
    447 
    448 inline bool read() {
    449 	if(!(cin >> n >> m))
    450 		return false;
    451 	assert(cin >> a >> b >> c);
    452 	fore(i, 0, m) {
    453 		int u, v;
    454 		assert(scanf("%d%d", &u, &v) == 2);
    455 		
    456 		g[u].push_back(v);
    457 		g[v].push_back(u);
    458 	}
    459 	return true;
    460 }
    461 
    462 vector<uli> ps[N];
    463 
    464 inline uli getSum(int v, int l, int r) {
    465 	return ps[v][r] - ps[v][l];
    466 }
    467 
    468 const int MX = 700;
    469 int id[N];
    470 
    471 const int B = 1111;
    472 bitset<N> has[B];
    473 int szh = 0;
    474 
    475 inline void solve() {
    476 	memset(id, -1, sizeof id);
    477 	szh = 0;
    478 	fore(v, 0, n) {
    479 		sort(g[v].begin(), g[v].end());
    480 		
    481 		ps[v].assign(sz(g[v]) + 1, 0);
    482 		fore(i, 0, sz(g[v]))
    483 			ps[v][i + 1] = ps[v][i] + g[v][i];
    484 		
    485 		if(sz(g[v]) >= MX) {
    486 			assert(szh < B);
    487 			id[v] = szh++;
    488 			
    489 			for(int to : g[v])
    490 				has[id[v]][to] = 1;
    491 		}
    492 	}
    493 	
    494 	uli all = 0;
    495 	fore(v, 0, n) {
    496 		uli lw = v, gr = n - v - 1;
    497 		all += a * v * (gr * (gr - 1) / 2);
    498 		all += b * v * (lw * gr);
    499 		all += c * v * (lw * (lw - 1) / 2);
    500 	}
    501 	
    502 	uli sub1 = 0;
    503 	fore(v, 0, n) {
    504 		for(int to : g[v]) {
    505 			if(to > v)
    506 				break;
    507 			
    508 			uli cnt = to;
    509 			uli sum = cnt * (cnt - 1) / 2;
    510 			sub1 += a * sum + cnt * (b * to + c * v);
    511 			
    512 			cnt = v - to - 1;
    513 			sum = (2 * to + cnt + 1) * cnt / 2;
    514 			sub1 += b * sum + cnt * (a * to + c * v);
    515 		}
    516 		
    517 		uli sum = 0;
    518 		fore(i, 0, sz(g[v])) {
    519 			if(g[v][i] > v)
    520 				break;
    521 			
    522 			uli cnt = i;
    523 			sub1 -= a * sum + cnt * (b * g[v][i] + c * v);
    524 			sum += g[v][i];
    525 		}
    526 	}
    527 	all -= sub1;
    528 	
    529 	uli sub2 = 0;
    530 	uli cntE = 0, sumE = 0;
    531 	fore(v, 0, n) {
    532 		sub2 += sumE + cntE * c * v;
    533 		for(int to : g[v]) {
    534 			if(to > v)
    535 				break;
    536 			
    537 			cntE++;
    538 			sumE += a * to + b * v;
    539 		}
    540 	}
    541 	
    542 	fore(v, 0, n) {
    543 		for(int to : g[v]) {
    544 			if(to > v)
    545 				break;
    546 			
    547 			int pos = int(lower_bound(g[to].begin(), g[to].end(), to) - g[to].begin());
    548 			sub2 -= a * getSum(to, 0, pos) + pos * (b * to + c * v);
    549 			
    550 			int pos2 = int(lower_bound(g[to].begin(), g[to].end(), v) - g[to].begin());
    551 			sub2 -= b * getSum(to, pos, pos2) + (pos2 - pos) * (a * to + c * v);
    552 		}
    553 	}
    554 	
    555 	vector<char> curh(n + 5, 0);
    556 	fore(v, 0, n) {
    557 		if(id[v] == -1) {
    558 			fore(i2, 0, sz(g[v])) {
    559 				int u2 = g[v][i2];
    560 				if(u2 > v)
    561 					break;
    562 				
    563 				if(id[u2] != -1) {
    564 					fore(i1, 0, i2) {
    565 						int u1 = g[v][i1];
    566 						if(has[id[u2]][u1])
    567 							sub2 += a * u1 + b * u2 + c * v;
    568 					}
    569 				} else {
    570 					for(int to : g[u2]) {
    571 						if(to > u2)
    572 							break;
    573 						curh[to] = 1;
    574 					}
    575 					fore(i1, 0, i2) {
    576 						int u1 = g[v][i1];
    577 						if(curh[u1])
    578 							sub2 += a * u1 + b * u2 + c * v;
    579 					}
    580 					for(int to : g[u2]) {
    581 						if(to > u2)
    582 							break;
    583 						curh[to] = 0;
    584 					}
    585 				}
    586 			}
    587 		} else {
    588 			fore(u2, 0, v) {
    589 				if(!has[id[v]][u2])
    590 					continue;
    591 				for(int u1 : g[u2]) {
    592 					if(u1 > u2)
    593 						break;
    594 					if(has[id[v]][u1])
    595 						sub2 += a * u1 + b * u2 + c * v;
    596 				}
    597 			}
    598 		}
    599 	}
    600 	all -= sub2;
    601 	cout << all << endl;
    602 }
    603 
    604 int main(){
    605 #ifdef _DEBUG
    606 	freopen("input.txt", "r", stdin);
    607 	int tt = clock();
    608 #endif
    609 	cout << fixed << setprecision(10);
    610 
    611 	if(read()) {
    612 		solve();
    613 #ifdef _DEBUG
    614 		cerr << "TIME = " << clock() - tt << endl;
    615 #endif
    616 	}
    617 	return 0;
    618 }
    619 ```