codeforces-scrape

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

1234.md (7053B)


      1 Source: https://codeforces.com/blog/entry/70233
      2 
      3 Suddenly, all problems expect A and D were invented by me. The author of A and D is [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1234A - Equalize Prices Again](/contest/1234/problem/A "Codeforces Round 590 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int q;
     25 	cin >> q;
     26 	for (int i = 0; i < q; ++i) {
     27 		int n;
     28 		cin >> n;
     29 		int sum = 0;
     30 		for (int j = 0; j < n; ++j) {
     31 			int x;
     32 			cin >> x;
     33 			sum += x;
     34 		}
     35 		cout << (sum + n - 1) / n << endl;
     36 	}
     37 	
     38 	return 0;
     39 }
     40 ```
     41 
     42 [1234B1 - Social Network (easy version)](/contest/1234/problem/B1 "Codeforces Round 590 (Div. 3)")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 int main() {
     56 #ifdef _DEBUG
     57 	freopen("input.txt", "r", stdin);
     58 //	freopen("output.txt", "w", stdout);
     59 #endif
     60 	
     61 	int n, k;
     62 	cin >> n >> k;
     63 	vector<int> ids;
     64 	for (int i = 0; i < n; ++i) {
     65 		int id;
     66 		cin >> id;
     67 		if (find(ids.begin(), ids.end(), id) == ids.end()) {
     68 			if (int(ids.size()) >= k) ids.pop_back();
     69 			ids.insert(ids.begin(), id);
     70 		}
     71 	}
     72 	
     73 	cout << ids.size() << endl;
     74 	for (auto it : ids) cout << it << " ";
     75 	cout << endl;
     76 	
     77 	return 0;
     78 }
     79 ```
     80 
     81 [1234B2 - Social Network (hard version)](/contest/1234/problem/B2 "Codeforces Round 590 (Div. 3)")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 int main() {
     95 #ifdef _DEBUG
     96 	freopen("input.txt", "r", stdin);
     97 //	freopen("output.txt", "w", stdout);
     98 #endif
     99 	
    100 	int n, k;
    101 	cin >> n >> k;
    102 	
    103 	queue<int> q;
    104 	set<int> vals;
    105 	for (int i = 0; i < n; ++i) {
    106 		int id;
    107 		cin >> id;
    108 		if (!vals.count(id)) {
    109 			if (int(q.size()) >= k) {
    110 				int cur = q.front();
    111 				q.pop();
    112 				vals.erase(cur);
    113 			}
    114 			vals.insert(id);
    115 			q.push(id);
    116 		}
    117 	}
    118 	
    119 	vector<int> res;
    120 	while (!q.empty()) {
    121 		res.push_back(q.front());
    122 		q.pop();
    123 	}
    124 	reverse(res.begin(), res.end());
    125 	cout << res.size() << endl;
    126 	for (auto it : res) cout << it << " ";
    127 	cout << endl;
    128 	
    129 	return 0;
    130 }
    131 ```
    132 
    133 [1234C - Pipes](/contest/1234/problem/C "Codeforces Round 590 (Div. 3)")
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 
    144 using namespace std;
    145 
    146 int main() {
    147 #ifdef _DEBUG
    148 	freopen("input.txt", "r", stdin);
    149 //	freopen("output.txt", "w", stdout);
    150 #endif
    151 	
    152 	int q;
    153 	cin >> q;
    154 	for (int i = 0; i < q; ++i) {
    155 		int n;
    156 		string s[2];
    157 		cin >> n >> s[0] >> s[1];
    158 		int row = 0;
    159 		int pos = 0;
    160 		for (pos = 0; pos < n; ++pos) {
    161 			if (s[row][pos] >= '3') {
    162 				if (s[row ^ 1][pos] < '3') {
    163 					break;
    164 				} else {
    165 					row ^= 1;
    166 				}
    167 			}
    168 		}
    169 		if (pos == n && row == 1) {
    170 			cout << "YES" << endl;
    171 		} else {
    172 			cout << "NO" << endl;
    173 		}
    174 	}
    175 	
    176 	return 0;
    177 }
    178 ```
    179 
    180 [1234D - Distinct Characters Queries](/contest/1234/problem/D "Codeforces Round 590 (Div. 3)")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 using namespace std;
    192 
    193 int main() {
    194 #ifdef _DEBUG
    195 	freopen("input.txt", "r", stdin);
    196 //	freopen("output.txt", "w", stdout);
    197 #endif
    198 	
    199 	string s;
    200 	cin >> s;
    201 	vector<set<int>> poss(26);
    202 	for (int i = 0; i < int(s.size()); ++i) {
    203 		poss[s[i] - 'a'].insert(i);
    204 	}
    205 	
    206 	int q;
    207 	cin >> q;
    208 	for (int i = 0; i < q; ++i) {
    209 		int tp;
    210 		cin >> tp;
    211 		if (tp == 1) {
    212 			int pos;
    213 			char c;
    214 			cin >> pos >> c;
    215 			--pos;
    216 			poss[s[pos] - 'a'].erase(pos);
    217 			s[pos] = c;
    218 			poss[s[pos] - 'a'].insert(pos);
    219 		} else {
    220 			int l, r;
    221 			cin >> l >> r;
    222 			--l, --r;
    223 			int cnt = 0;
    224 			for (int c = 0; c < 26; ++c) {
    225 				auto it = poss[c].lower_bound(l);
    226 				if (it != poss[c].end() && *it <= r) ++cnt;
    227 			}
    228 			cout << cnt << endl;
    229 		}
    230 	}
    231 	
    232 	return 0;
    233 }
    234 ```
    235 
    236 [1234E - Special Permutations](/contest/1234/problem/E "Codeforces Round 590 (Div. 3)")
    237 
    238 **Tutorial**
    239 
    240 Tutorial is loading...
    241 
    242 **Solution**
    243 
    244 ```
    245 #include <bits/stdc++.h>
    246 
    247 using namespace std;
    248 
    249 int main() {
    250 #ifdef _DEBUG
    251 	freopen("input.txt", "r", stdin);
    252 //	freopen("output.txt", "w", stdout);
    253 #endif
    254 	
    255 	int n, m;
    256 	cin >> n >> m;
    257 	vector<int> a(m);
    258 	for (int i = 0; i < m; ++i) {
    259 		cin >> a[i];
    260 		--a[i];
    261 	}
    262 	
    263 	vector<long long> res(n);
    264 	for (int j = 0; j < m - 1; ++j) {
    265 		res[0] += abs(a[j] - a[j + 1]);
    266 	}
    267 	
    268 	vector<int> cnt(n);
    269 	vector<vector<int>> adj(n);
    270 	for (int i = 0; i < m - 1; ++i) {
    271 		int l = a[i], r = a[i + 1];
    272 		if (l != r) {
    273 			adj[l].push_back(r);
    274 			adj[r].push_back(l);
    275 		}
    276 		if (l > r) swap(l, r);
    277 		if (r - l < 2) continue;
    278 		++cnt[l + 1];
    279 		--cnt[r];
    280 	}
    281 	for (int i = 0; i < n - 1; ++i) {
    282 		cnt[i + 1] += cnt[i];
    283 	}
    284 	
    285 	for (int i = 1; i < n; ++i) {
    286 		res[i] = res[0] - cnt[i];
    287 		for (auto j : adj[i]) {
    288 			res[i] -= abs(i - j);
    289 			res[i] += j + (j < i);
    290 		}
    291 	}
    292 	
    293 	for (int i = 0; i < n; ++i) {
    294 		cout << res[i] << " ";
    295 	}
    296 	cout << endl;
    297 	
    298 	return 0;
    299 }
    300 ```
    301 
    302 [1234F - Yet Another Substring Reverse](/contest/1234/problem/F "Codeforces Round 590 (Div. 3)")
    303 
    304 **Tutorial**
    305 
    306 Tutorial is loading...
    307 
    308 **Solution**
    309 
    310 ```
    311 #include <bits/stdc++.h>
    312 
    313 using namespace std;
    314 
    315 int main() {
    316 #ifdef _DEBUG
    317 	freopen("input.txt", "r", stdin);
    318 //	freopen("output.txt", "w", stdout);
    319 #endif
    320 	
    321 	string s;
    322 	cin >> s;
    323 	
    324 	vector<int> dp(1 << 20);
    325 	for (int i = 0; i < int(s.size()); ++i) {
    326 		vector<bool> used(20);
    327 		int mask = 0;
    328 		for (int j = 0; i + j < int(s.size()); ++j) {
    329 			if (used[s[i + j] - 'a']) break;
    330 			used[s[i + j] - 'a'] = true;
    331 			mask |= 1 << (s[i + j] - 'a');
    332 			dp[mask] = __builtin_popcount(mask);
    333 		}
    334 	}
    335 	
    336 	for (int mask = 0; mask < (1 << 20); ++mask) {
    337 		for (int pos = 0; pos < 20; ++pos) {
    338 			if ((mask >> pos) & 1) {
    339 				dp[mask] = max(dp[mask], dp[mask ^ (1 << pos)]);
    340 			}
    341 		}
    342 	}
    343 	
    344 	int ans = 0;
    345 	for (int mask = 0; mask < (1 << 20); ++mask) {
    346 		if (dp[mask] == __builtin_popcount(mask)) {
    347 			int comp = ~mask & ((1 << 20) - 1);
    348 			ans = max(ans, dp[mask] + dp[comp]);
    349 		}
    350 	}
    351 	
    352 	cout << ans << endl;
    353 	
    354 	return 0;
    355 }
    356 ```
    357 
    358 **WA?**
    359 
    360 ```
    361 #include <bits/stdc++.h>
    362 
    363 using namespace std;
    364 
    365 int main() {
    366 #ifdef _DEBUG
    367 	freopen("input.txt", "r", stdin);
    368 //	freopen("output.txt", "w", stdout);
    369 #endif
    370 
    371 	int tt = clock();
    372 	
    373 	string s;
    374 	cin >> s;
    375 	
    376 	vector<int> dp(1 << 20);
    377 	vector<int> masks;
    378 	for (int i = 0; i < int(s.size()); ++i) {
    379 		vector<bool> used(20);
    380 		int mask = 0;
    381 		for (int j = 0; i + j < int(s.size()); ++j) {
    382 			if (used[s[i + j] - 'a']) break;
    383 			used[s[i + j] - 'a'] = true;
    384 			mask |= 1 << (s[i + j] - 'a');
    385 			masks.push_back(mask);
    386 		}
    387 	}
    388 	sort(masks.begin(), masks.end());
    389 	masks.resize(unique(masks.begin(), masks.end()) - masks.begin());
    390 	sort(masks.begin(), masks.end(), [](int x, int y){
    391 		return __builtin_popcount(x) > __builtin_popcount(y);
    392 	});
    393 	
    394 	int ans = __builtin_popcount(masks[0]);
    395 	for (int i = 0; i < int(masks.size()); ++i) {
    396 		if (clock() - tt > 1900) {
    397 			break;
    398 		}
    399 		for (int j = i + 1; j < int(masks.size()); ++j) {
    400 			if (!(masks[i] & masks[j])) {
    401 				ans = max(ans, __builtin_popcount(masks[i]) + __builtin_popcount(masks[j]));
    402 				break;
    403 			}
    404 		}
    405 	}
    406 	
    407 	cout << ans << endl;
    408 	
    409 	return 0;
    410 }
    411 ```