codeforces-scrape

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

2267.md (10270B)


      1 Source: https://codeforces.com/blog/entry/157126
      2 
      3 Thanks a lot for participating!
      4 
      5 [2267A - Turn Into a Palindrome](/contest/2267/problem/A "Codeforces Round 1123 (Div. 2)")
      6 
      7 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ")
      8 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ")
      9 
     10 **Solution**
     11 
     12 Tutorial is loading...
     13 
     14 **Implementation**
     15 
     16 ```
     17 #include <bits/stdc++.h>
     18 
     19 using namespace std;
     20 
     21 signed main() {
     22     int T;
     23     cin >> T;
     24     while (T--) {
     25         int n;
     26         cin >> n;
     27         char c; cin >> c;
     28         string s; cin >> s;
     29         int ans = 0;
     30         for (int i = 0; i < n / 2; ++i) {
     31             if (s[i] == s[n - i - 1]) continue;
     32             if (s[i] == c || s[n - i - 1] == c) ans++;
     33             else ans+=2;
     34         }
     35         cout << ans << '\n';
     36     }
     37 }
     38 ```
     39 
     40 **Did you like the problem?**
     41 
     42 * Great problem
     43 * Good problem
     44 * Bad problem
     45 * Didn't solve
     46 
     47 [2267B - Fashionable Array](/contest/2267/problem/B "Codeforces Round 1123 (Div. 2)")
     48 
     49 * Idea: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF")
     50 * Solution + Editorial: [YF_YUSUF](/profile/YF_YUSUF "Expert YF_YUSUF"), [KluydQ](/profile/KluydQ "Expert KluydQ")
     51 
     52 **Solution**
     53 
     54 Tutorial is loading...
     55 
     56 **Implementation**
     57 
     58 ```
     59 #include <bits/stdc++.h>
     60 
     61 using namespace std;
     62 
     63 int n, a[101], cnt[101];
     64 
     65 void solve()
     66 {
     67 	cin >> n;
     68 	
     69 	for(int i = 1; i <= n; i ++)
     70 	{
     71 		cin >> a[i];
     72 		cnt[a[i]] ++;
     73 	}
     74 	for(int i = 1; i <= n; i ++)
     75 	{
     76 		for(int j = 100; j >= 1; j --)
     77 		{
     78 			if(cnt[j] >= i) cout << j << ' ';
     79 		}
     80 	}
     81 	for(int i = 1; i <= n; i ++) cnt[a[i]] = 0;
     82 	
     83 	cout << '\n';
     84 }
     85 int main()
     86 {
     87 	int t;
     88 	cin >> t;
     89 	while(t --) solve();
     90 }
     91 ```
     92 
     93 **Did you like the problem?**
     94 
     95 * Great problem
     96 * Good problem
     97 * Bad problem
     98 * Didn't solve
     99 
    100 [2267C - GCD Treasury](/contest/2267/problem/C "Codeforces Round 1123 (Div. 2)")
    101 
    102 * Idea: [Dibamboo](/profile/Dibamboo "Pupil Dibamboo")
    103 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ")
    104 
    105 **Solution**
    106 
    107 Tutorial is loading...
    108 
    109 **Implementation**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 #define ll long long
    114 
    115 const int N = 3e5 + 12;
    116 using namespace std;
    117 
    118 int n, x, a[N], p[N];
    119 ll cnt[N];
    120 
    121 vector <int> vc[N];
    122 
    123 void solve()
    124 {
    125 	cin >> n >> x;
    126 	
    127 	for(int i = 1; i <= n; i ++)
    128 	{
    129 		cin >> a[i];
    130 		int r = a[i];
    131 		a[i] = __gcd(a[i], x);
    132 		
    133 		for(auto j : vc[a[i]])
    134 		{
    135 			cnt[j] += r;
    136 		}
    137 	}
    138 	ll ans = 0;
    139 	
    140 	for(auto j : vc[x])
    141 	{
    142 		ans = max(ans, cnt[j]);
    143 	}
    144 	for(int i = 1; i <= n; i ++)
    145 	{
    146 		for(auto j : vc[a[i]]) cnt[j] = 0;
    147 	}
    148 	cout << ans << '\n';
    149 }
    150 signed main()
    151 {
    152 	ios_base::sync_with_stdio(0), cin.tie(0);
    153 	
    154 	for(int i = 2; i <= N - 12; i ++)
    155 	{
    156 		if(!p[i])
    157 		{
    158 			for(int j = i; j <= N - 12; j += i)
    159 			{
    160 				p[j] = 1;
    161 				vc[j].push_back(i);
    162 			}
    163 		}
    164 	}
    165 	int test = 0;
    166 	if(!test) cin >> test;
    167 	while(test --) solve();
    168 }
    169 // solved by KluydQ
    170 ```
    171 
    172 **Did you like the problem?**
    173 
    174 * Great problem
    175 * Good problem
    176 * Bad problem
    177 * Didn't solve
    178 
    179 [2267D - Backrooms Hill](/contest/2267/problem/D "Codeforces Round 1123 (Div. 2)")
    180 
    181 * Idea: [Aldk](/profile/Aldk "Candidate Master Aldk")
    182 * Solution + Editorial: [Aldk](/profile/Aldk "Candidate Master Aldk"), [KluydQ](/profile/KluydQ "Expert KluydQ")
    183 
    184 **Solution**
    185 
    186 Tutorial is loading...
    187 
    188 **Implementation**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 
    193 using namespace std;
    194 
    195 void solve()
    196 {
    197 	int n;
    198 	cin >> n;
    199 	
    200 	int a[n + 5];
    201 	int pos[n + 5];
    202 	
    203 	for(int i = 1; i <= n; i ++)
    204 	{
    205 		cin >> a[i];
    206 		pos[a[i]] = i % 2;
    207 	}
    208 	int balance = 0;
    209 	
    210 	for(int x = n; x > 0; x --)
    211 	{
    212 		if(pos[x] % 2 == 0) balance ++;
    213 		if(pos[x] % 2 == 1) balance --;
    214 		
    215 		if(abs(balance) > 1)
    216 		{
    217 			cout << "NO\n";
    218 			return;
    219 		}
    220 	}
    221 	cout << "YES\n";
    222 }
    223 int main()
    224 {
    225 	int t;
    226 	cin >> t;
    227 	while(t --) solve();
    228 }
    229 ```
    230 
    231 **Did you like the problem?**
    232 
    233 * Great problem
    234 * Good problem
    235 * Bad problem
    236 * Didn't solve
    237 
    238 [2267E - Clean Substrings](/contest/2267/problem/E "Codeforces Round 1123 (Div. 2)")
    239 
    240 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ")
    241 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ")
    242 
    243 **Solution**
    244 
    245 Tutorial is loading...
    246 
    247 **Implementation**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251 
    252 #define int long long
    253 #define sz(x) (int)(x.size())
    254 #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
    255 #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
    256 
    257 using namespace std;
    258 
    259 const int N = 2e5 + 12;
    260 const int mod = 1e9 + 7;
    261 
    262 int n, q, ans, cnt0, cnt1, pr[N];
    263 string s;
    264 
    265 void solve()
    266 {
    267 	cin >> n >> q >> s;
    268     ans = cnt0 = cnt1 = 0;
    269 	
    270 	FOR(i, 1, n - 1, 1)
    271 	{
    272 		pr[i] = 0;
    273 		
    274 		if(s[i - 1] != s[i])
    275 		{
    276 			pr[i] = 1;
    277 			ans += i * (n - i);
    278 		}
    279 	}
    280 	FOR(i, 0, n - 1, 1)
    281 	{
    282 	    if(s[i] == '0') cnt0 ++;
    283 	    if(s[i] == '1') cnt1 ++;
    284 	}
    285 	cout << (ans + cnt0 * cnt1) / 2 << ' ';
    286 	
    287 	FOR(i, 1, q, 1)
    288 	{
    289 		int pos;
    290 		cin >> pos;
    291 		
    292 		if(pos != 1)
    293 		{
    294 			if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1);
    295 			else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1);
    296 		}
    297 		if(pos != n)
    298 		{
    299 			if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos);
    300 			else pr[pos] = 0, ans -= pos * (n - pos);
    301 		}
    302 		if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1';
    303 		else cnt1 --, cnt0 ++, s[pos - 1] = '0';
    304 		
    305 		cout << (ans + cnt0 * cnt1) / 2 << ' ';
    306 	}
    307 	cout << '\n';
    308 }
    309 signed main()
    310 {
    311 	ios_base::sync_with_stdio(0), cin.tie(0);
    312 	
    313 	int t = 0;
    314 	if(!t) cin >> t;
    315 	while(t --) solve();
    316 }
    317 ```
    318 
    319 **Did you like the problem?**
    320 
    321 * Great problem
    322 * Good problem
    323 * Bad problem
    324 * Didn't solve
    325 
    326 [2267F1 - XOR Transformations (Easy Version)](/contest/2267/problem/F1 "Codeforces Round 1123 (Div. 2)")
    327 
    328 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ")
    329 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ")
    330 
    331 **Solution**
    332 
    333 Tutorial is loading...
    334 
    335 **Implementation**
    336 
    337 ```
    338 #include <bits/stdc++.h>
    339 
    340 using namespace std;
    341 
    342 const int N = 2048;
    343 int n, m, tim, a[N], cnt[N], ans[N];
    344 
    345 void transform()
    346 {
    347 	vector <int> v;
    348 	
    349 	for(int i = 1; i <= n; i ++)
    350 	{
    351 		for(int j = i + 1; j <= n; j ++)
    352 		{
    353 			v.push_back(a[i] ^ a[j]);
    354 		}
    355 	}
    356 	sort(v.begin(), v.end());
    357 	for(int i = 1; i <= n; i ++) a[i] = v[i - 1];
    358 }
    359 void solve()
    360 {
    361 	cin >> n >> m;
    362 	
    363 	for(int i = 1; i <= n; i ++)
    364 	{
    365 		cin >> a[i];
    366 	}
    367 	sort(a + 1, a + n + 1);
    368 	int lim = 0;
    369 	
    370 	ans[lim] = a[n] - a[1];
    371 		
    372 	while(a[n] != 0)
    373 	{
    374 		lim ++, transform();
    375 		ans[lim] = a[n] - a[1];
    376 	}
    377 	for(int i = 1; i <= m; i ++)
    378 	{
    379 		int x;
    380 		cin >> x;
    381 		
    382 		if(x >= lim) cout << ans[lim] << '\n';
    383 		else cout << ans[x] << '\n';
    384 	}
    385 }
    386 signed main()
    387 {
    388 	ios_base::sync_with_stdio(0), cin.tie(0);
    389 	
    390 	int test = 0;
    391 	if(!test) cin >> test;
    392 	while(test --) solve();
    393 }
    394 ```
    395 
    396 **Did you like the problem?**
    397 
    398 * Great problem
    399 * Good problem
    400 * Bad problem
    401 * Didn't solve
    402 
    403 [2267F2 - XOR Transformations (Hard Version)](/contest/2267/problem/F2 "Codeforces Round 1123 (Div. 2)")
    404 
    405 * Idea: [KluydQ](/profile/KluydQ "Expert KluydQ")
    406 * Solution + Editorial: [KluydQ](/profile/KluydQ "Expert KluydQ")
    407 
    408 **Solution**
    409 
    410 Tutorial is loading...
    411 
    412 **Implementation**
    413 
    414 ```
    415 #include <bits/stdc++.h>
    416 
    417 using namespace std;
    418 
    419 const int N = 3e5 + 12;
    420 
    421 int n, m, tim, a[N], cnt[N], ans[N];
    422 int t[N * 30], son[N * 30][2];
    423 
    424 void update(int x, int v = 1)
    425 {
    426 	t[v] ++;
    427 	
    428 	for(int i = 29; i >= 0; i --)
    429 	{
    430 		if((x >> i) & 1)
    431 		{
    432 			if(!son[v][1]) son[v][1] = ++ tim;
    433 			v = son[v][1];
    434 		}
    435 		else
    436 		{
    437 			if(!son[v][0]) son[v][0] = ++ tim;
    438 			v = son[v][0];
    439 		}
    440 		t[v] ++;
    441 	}
    442 }
    443 int get(int x, int k, int v = 1)
    444 {
    445 	int res = 0;
    446 	
    447 	for(int i = 29; i >= 0; i --)
    448 	{
    449 		int b = (x >> i) & 1;
    450 		
    451 		if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b;
    452 		else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1);
    453 	}
    454 	return res ^ x;
    455 }
    456 void transform()
    457 {
    458 	for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0;
    459 	set <pair <int, int>> st; tim = 1;
    460 	
    461 	for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2;
    462 	for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i});
    463 	
    464 	vector <int> upd;
    465 	
    466 	for(int _ = 1; _ <= 2 * n; _ ++)
    467 	{
    468 		auto it = st.begin();
    469 		int i = (*it).second;
    470 		
    471 		upd.push_back((*it).first);
    472 		st.erase(it), cnt[i] ++;
    473 		
    474 		if(cnt[i] > n) continue;
    475 		st.insert({get(a[i], cnt[i]), i});
    476 	}
    477 	for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2];
    478 }
    479 void solve()
    480 {
    481 	cin >> n >> m;
    482 	
    483 	for(int i = 1; i <= n; i ++)
    484 	{
    485 		cin >> a[i];
    486 	}
    487 	sort(a + 1, a + n + 1);
    488 	int lim = 0;
    489 	
    490 	ans[lim] = a[n] - a[1];
    491 	
    492 	while(a[n] != 0)
    493 	{
    494 		lim ++, transform();
    495 		ans[lim] = a[n] - a[1];
    496 	}
    497 	for(int i = 1; i <= m; i ++)
    498 	{
    499 		int x;
    500 		cin >> x;
    501 		
    502 		if(x >= lim) cout << ans[lim] << '\n';
    503 		else cout << ans[x] << '\n';
    504 	}
    505 }
    506 signed main()
    507 {
    508 	ios_base::sync_with_stdio(0), cin.tie(0);
    509 	
    510 	int test = 0;
    511 	if(!test) cin >> test;
    512 	while(test --) solve();
    513 }
    514 ```
    515 
    516 **Did you like the problem?**
    517 
    518 * Great problem
    519 * Good problem
    520 * Bad problem
    521 * Didn't solve
    522 
    523 [2267G - New LRT](/contest/2267/problem/G "Codeforces Round 1123 (Div. 2)")
    524 
    525 * Idea: [Aldk](/profile/Aldk "Candidate Master Aldk")
    526 * Solution + Editorial: [Aldk](/profile/Aldk "Candidate Master Aldk"), [KluydQ](/profile/KluydQ "Expert KluydQ")
    527 
    528 **Solution**
    529 
    530 Tutorial is loading...
    531 
    532 **Implementation**
    533 
    534 ```
    535 #include <bits/stdc++.h>
    536 
    537 #define sz(x) (int)(x.size())
    538 #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
    539 #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
    540 
    541 using namespace std;
    542 
    543 const int N = (1 << 20) + 5;
    544 const int mod = 1e9 + 7;
    545 
    546 int n, m, c[N], dp[N], cnt[N], st[N][21];
    547 
    548 void add(int &x, int y)
    549 {
    550     x += y;
    551     if(x >= mod) x -= mod;
    552 }
    553 void solve()
    554 {
    555 	cin >> n >> m;
    556 	
    557 	FOR( i, 1, m, 1 )
    558 	{
    559 		cin >> c[i];
    560 	}
    561 	dp[0] = cnt[0] = 1;
    562 	
    563 	FOR( i, 1, n, 1 )
    564 	{
    565 		st[i][0] = 0;
    566 		
    567 		FOR( j, 0, 19, 1 )
    568 		{
    569 			st[i][j + 1] = st[i][j];
    570 			if(!((m >> j) & 1) || i < (1 << j)) continue;
    571 			
    572 			else
    573 			{
    574 			    add(st[i][j + 1], st[i - (1 << j)][j]);
    575 			    add(st[i][j + 1], dp[i - (1 << j)]);
    576 			}
    577 		}
    578 		dp[i] = st[i][20];
    579 	}
    580 	FOR( i, 1, n, 1 )
    581 	{
    582 		st[i][0] = 0;
    583 		
    584 		FOR( j, 0, 19, 1 )
    585 		{
    586 		    st[i][j + 1] = st[i][j];
    587 			if(!((m >> j) & 1) || i < (1 << j)) continue;
    588 			
    589 			else
    590 			{
    591 			    add(st[i][j + 1], st[i - (1 << j)][j]);
    592 			    add(st[i][j + 1], cnt[i - (1 << j)]);
    593 			}
    594 		}
    595 		cnt[i] = st[i][20];
    596 		add(cnt[i], dp[i]);
    597 	}
    598 	int ans = 0;
    599 	
    600 	FOR( i, 1, m, 1 )
    601 	{
    602 		if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod);
    603 	}
    604 	cout << ans << '\n';
    605 }
    606 signed main()
    607 {
    608     ios_base::sync_with_stdio(0), cin.tie(0);
    609     
    610 	int t = 0;
    611 	if(!t) cin >> t;
    612 	while(t --) solve();
    613 }
    614 ```
    615 
    616 **Did you like the problem?**
    617 
    618 * Great problem
    619 * Good problem
    620 * Bad problem
    621 * Didn't solve