codeforces-scrape

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

1879.md (8682B)


      1 Source: https://codeforces.com/blog/entry/120773
      2 
      3 [1879A - Rigged!](/contest/1879/problem/A "Educational Codeforces Round 155 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 const int N = 109;
     19 
     20 int t;
     21 int n;
     22 int s[N], e[N];
     23  
     24 int main() {
     25     cin >> t;
     26     for (int tc = 0; tc < t; ++tc) {
     27         cin >> n;
     28         for (int i = 0; i < n; ++i) {
     29             cin >> s[i] >> e[i];
     30         }
     31         
     32         bool ok = true;
     33         for (int i = 1; i < n; ++i) 
     34             if (s[i] >= s[0] && e[i] >= e[0])
     35                 ok = false;
     36         
     37         if (!ok) {
     38             puts("-1");
     39             continue;
     40         }
     41         
     42         cout << s[0] << endl;
     43     }
     44     return 0;
     45 }
     46 ```
     47 
     48 [1879B - Chips on the Board](/contest/1879/problem/B "Educational Codeforces Round 155 (Rated for Div. 2)")
     49 
     50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Solution (Neon)**
     57 
     58 ```
     59 #include <bits/stdc++.h>
     60  
     61 using namespace std;
     62 
     63 using li = long long;
     64 
     65 int main() {
     66   ios::sync_with_stdio(false); cin.tie(0);
     67   int t;
     68   cin >> t;
     69   while (t--) {
     70     int n;
     71     cin >> n;
     72     vector<li> a(n), b(n);
     73     for (auto& x : a) cin >> x;
     74     for (auto& x : b) cin >> x;
     75     li mnA = *min_element(a.begin(), a.end());
     76     li sA = accumulate(a.begin(), a.end(), 0LL);
     77     li mnB = *min_element(b.begin(), b.end());
     78     li sB = accumulate(b.begin(), b.end(), 0LL);
     79     li ans = min(mnA * n + sB, mnB * n + sA);
     80     cout << ans << '\n';
     81   }
     82 }
     83 ```
     84 
     85 [1879C - Make it Alternating](/contest/1879/problem/C "Educational Codeforces Round 155 (Rated for Div. 2)")
     86 
     87 Idea: [Roms](/profile/Roms "Master Roms")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (Roms)**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 const int MOD = 998'244'353;
    101 
    102 void upd(int &a, int b) {
    103     a = (a * 1LL * b) % MOD;
    104 }
    105 
    106 int t;
    107 string s;
    108 
    109 int main() {
    110 	cin >> t;
    111 	for (int tc = 0; tc < t; ++tc) {
    112 	    cin >> s;
    113 	    int res = 1;
    114 	    int k = s.size();
    115 	    int n = s.size();
    116 	    for (int l = 0; l < n; ) {
    117 	        int r = l + 1;
    118 	        while(r < n && s[l] == s[r])
    119 	            ++r;
    120             upd(res, r - l);
    121             --k;
    122             l = r;
    123 	    }
    124 	    
    125 	    for (int i = 1; i <= k; ++i)
    126 	        upd(res, i);
    127         cout << k << ' ' << res << endl;
    128 	}
    129 }
    130 ```
    131 
    132 [1879D - Sum of XOR Functions](/contest/1879/problem/D "Educational Codeforces Round 155 (Rated for Div. 2)")
    133 
    134 Idea: [Roms](/profile/Roms "Master Roms")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution (Roms)**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 
    145 using namespace std;
    146 
    147 const int N = 300005;
    148 const int MOD = 998244353;
    149 int n;
    150 int a[N];
    151 
    152 void add(int &a, int b) {
    153     a += b;
    154     if (a >= MOD)
    155         a -= MOD;
    156 }
    157 
    158 int sum(int a, int b) {
    159     a += b;
    160     if (a >= MOD)
    161         a -= MOD;
    162     if (a < 0)
    163         a += MOD;
    164     return a;
    165 }
    166 
    167 int mul(int a, int b) {
    168     return (a * 1LL * b) % MOD;
    169 }
    170 
    171 int main() {
    172     cin >> n;
    173     for (int i = 0; i < n; ++i)
    174         cin >> a[i];
    175     
    176     int res = 0;    
    177     for (int b = 0; b < 30; ++b) {
    178         int cur = 0;
    179         vector <int> cnt(2);
    180         vector <int> sumOfL(2);
    181         cnt[0] = 1;
    182         int x = 0;
    183         for (int i = 0; i < n; ++i) {
    184             x ^= ((a[i] >> b) & 1);
    185             int sumOfR = mul(cnt[x ^ 1], i + 1);
    186             add(cur, sum(sumOfR, -sumOfL[x ^ 1]));
    187             
    188             ++cnt[x];
    189             add(sumOfL[x], i + 1);
    190         }
    191         
    192         add(res, mul(1 << b, cur));
    193     }
    194     
    195     cout << res << endl;
    196 }
    197 ```
    198 
    199 [1879E - Interactive Game with Coloring](/contest/1879/problem/E "Educational Codeforces Round 155 (Rated for Div. 2)")
    200 
    201 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution (BledDest)**
    208 
    209 ```
    210 #include<bits/stdc++.h>
    211 
    212 using namespace std;
    213 
    214 const int N = 123;
    215 
    216 int n;
    217 int color[N];
    218 int countColors[N][N];
    219 int p[N];
    220 vector<int> g[N];
    221 int deg[N];
    222 
    223 void add_edge(int x, int y)
    224 {
    225 	g[x].push_back(y);
    226 	g[y].push_back(x);
    227 }
    228 
    229 bool tryTwoColors()
    230 {
    231 	int v1 = n + 1;
    232 	int v2 = n + 2;
    233 	for(int i = 2; i <= n; i++)
    234 	{
    235 		if(p[i] != 1)
    236 		{
    237 			add_edge(i, p[i]);
    238 		}
    239 	}
    240 	for(int i = 2; i <= n; i++)
    241 	{
    242 		if(deg[i] == 1)
    243 			add_edge(i, v1);
    244 	}
    245 	for(int i = 2; i <= n; i++)
    246 	{
    247 		if(p[i] != 1 && deg[p[i]] == 1)
    248 			add_edge(i, v2);
    249 	}
    250 	add_edge(v1, v2);
    251 	bool bad = false;
    252 	for(int i = 2; i <= n + 2; i++)
    253 		if(color[i] == 0)
    254 		{
    255 			color[i] = 1;
    256 			queue<int> q;
    257 			q.push(i);
    258 			while(!q.empty())
    259 			{
    260 				int k = q.front();
    261 				q.pop();
    262 				for(auto y : g[k])
    263 				{
    264 					if(color[y] == 0)
    265 					{
    266 						color[y] = 3 - color[k];
    267 						q.push(y);
    268 					}
    269 					else if(color[y] == color[k])
    270 						bad = true;
    271 				}
    272 			}
    273 		}
    274 	if(bad)
    275 		for(int i = 2; i <= n + 2; i++)
    276 			color[i] = 0;
    277 	return !bad;
    278 }
    279 
    280 void tryThreeColors()
    281 {
    282 	for(int i = 2; i <= n; i++)
    283 		if(p[i] == 1)
    284 			color[i] = 1;
    285 		else
    286 			color[i] = (color[p[i]] % 3) + 1;
    287 }
    288 
    289 int findVertex(const vector<int>& colors)
    290 {
    291 	int s = colors.size();
    292 	for(int i = 2; i <= n; i++)
    293 	{
    294 		if(vector<int>(countColors[i], countColors[i] + s) == colors)
    295 			return i;
    296 	}
    297 	return -1;
    298 }
    299 
    300 int main()
    301 {
    302 	cin >> n;
    303 	for(int i = 2; i <= n; i++)
    304 	{
    305 		cin >> p[i];
    306 		deg[p[i]]++;
    307 	}
    308 	
    309 	if(*max_element(p + 2, p + n + 1) == 1)
    310 	{
    311 		for(int i = 2; i <= n; i++)
    312 			color[i] = 1;
    313 	}
    314 	else if (!tryTwoColors())
    315 		tryThreeColors();
    316 	
    317 	int colorsUsed = *max_element(color + 2, color + n + 1);
    318 	
    319 	cout << colorsUsed << endl;
    320 	for(int i = 2; i <= n; i++)
    321 	{
    322 		cout << color[i];
    323 		if(i == n) cout << endl;
    324 		else cout << " ";
    325 	}
    326 	cout.flush();
    327 	
    328 	for(int i = 2; i <= n; i++)
    329 	{
    330 		countColors[i][color[i]]++;
    331 		countColors[p[i]][color[i]]++;
    332 	}
    333 	
    334 	while(true)
    335 	{
    336 		int resp;
    337 		cin >> resp;
    338 		if(resp == -1 || resp == 1)
    339 			exit(0);
    340 		vector<int> counts(colorsUsed + 1);
    341 		for(int i = 1; i <= colorsUsed; i++)
    342 			cin >> counts[i];
    343 		int v = findVertex(counts);
    344 		assert(v != -1);
    345 		cout << color[v] << endl;
    346 		cout.flush();
    347 	}
    348 }
    349 ```
    350 
    351 [1879F - Last Man Standing](/contest/1879/problem/F "Educational Codeforces Round 155 (Rated for Div. 2)")
    352 
    353 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    354 
    355 **Tutorial**
    356 
    357 Tutorial is loading...
    358 
    359 **Solution (awoo)**
    360 
    361 ```
    362 #include <bits/stdc++.h>
    363 
    364 #define forn(i, n) for (int i = 0; i < int(n); i++)
    365 
    366 using namespace std;
    367 
    368 int main() {
    369 	int t;
    370 	scanf("%d", &t);
    371 	while (t--){
    372 		int n;
    373 		scanf("%d", &n);
    374 		vector<int> h(n), a(n);
    375 		forn(i, n) scanf("%d", &h[i]);
    376 		forn(i, n) scanf("%d", &a[i]);
    377 		int mxa = *max_element(a.begin(), a.end()) + 1;
    378 		
    379 		int l = mxa == 1 ? 0 : (__lg(mxa - 1) + 1);
    380 		vector<vector<pair<int, int>>> st(l, vector<pair<int, int>>(mxa, make_pair(0, -1)));
    381 		vector<vector<int>> st2(l, vector<int>(mxa));
    382 		forn(i, n){
    383 			if (h[i] > st[0][a[i]].first){
    384 				st2[0][a[i]] = st[0][a[i]].first;
    385 				st[0][a[i]] = {h[i], i};
    386 			}
    387 			else if (h[i] > st2[0][a[i]]){
    388 				st2[0][a[i]] = h[i];
    389 			}
    390 		}
    391 		
    392 		auto combine = [&st, &st2](int i, int x, int y){
    393 			int mx = max(st[i][x].first, st[i][y].first);
    394 			if (mx == st[i][x].first)
    395 				return max(st2[i][x], st[i][y].first);
    396 			return max(st[i][x].first, st2[i][y]);
    397 		};
    398 		
    399 		for (int j = 1; j < l; ++j) forn(i, mxa){
    400 			if (i + (1 << (j - 1)) < mxa){
    401 				st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    402 				st2[j][i] = combine(j - 1, i, i + (1 << (j - 1)));
    403 			}
    404 			else{
    405 				st[j][i] = st[j - 1][i];
    406 				st2[j][i] = st2[j - 1][i];
    407 			}
    408 		}
    409 		vector<int> pw(mxa + 1);
    410 		for (int i = 2; i <= mxa; ++i) pw[i] = pw[i / 2] + 1;
    411 		
    412 		auto getmx = [&st, &pw](int l, int r){
    413 			int len = pw[r - l];
    414 			return max(st[len][l], st[len][r - (1 << len)]);
    415 		};
    416 		auto getmx2 = [&st, &st2, &pw, &combine](int l, int r){
    417 			int len = pw[r - l];
    418 			if (st[len][l].second != st[len][r - (1 << len)].second)
    419 				return combine(len, l, r - (1 << len));
    420 			return max(st2[len][l], st2[len][r - (1 << len)]);
    421 		};
    422 		
    423 		vector<long long> svmx(mxa), svmx2(mxa);
    424 		vector<int> svwho(mxa, -1);
    425 		for (int x = 1; x < mxa; ++x){
    426 			for (int l = 1; l < mxa; l += x){
    427 				int r = min(mxa, l + x);
    428 				int ac = (l - 1) / x + 1;
    429 				auto tmp = getmx(l, r);
    430 				long long mx = tmp.first * 1ll * ac;
    431 				int who = tmp.second;
    432 				long long mx2 = getmx2(l, r) * 1ll * ac;
    433 				if (who == -1) continue;
    434 				if (mx > svmx[x]){
    435 					svmx2[x] = svmx[x];
    436 					svmx[x] = mx;
    437 					svwho[x] = who;
    438 				}
    439 				else if (mx > svmx2[x]){
    440 					svmx2[x] = mx;
    441 				}
    442 				svmx2[x] = max(svmx2[x], mx2);
    443 			}
    444 		}
    445 		
    446 		vector<long long> ans(n);
    447 		forn(i, mxa) if (svwho[i] != -1)
    448 			ans[svwho[i]] = max(ans[svwho[i]], svmx[i] - svmx2[i]);
    449 		
    450 		forn(i, n) printf("%lld ", ans[i]);
    451 		puts("");
    452 	}
    453 	return 0;
    454 }
    455 ```