codeforces-scrape

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

1385.md (7471B)


      1 Source: https://codeforces.com/blog/entry/80257
      2 
      3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1385A - Three Pairwise Maximums](/contest/1385/problem/A "Codeforces Round 656 (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 t;
     25 	cin >> t;
     26 	while (t--) {
     27 		vector<int> a(3);
     28 		for (auto &it : a) cin >> it;
     29 		sort(a.begin(), a.end());
     30 		if (a[1] != a[2]) {
     31 			cout << "NO" << endl;
     32 		} else {
     33 			cout << "YES" << endl << a[0] << " " << a[0] << " " << a[2] << endl;
     34 		}
     35 	}
     36 	
     37 	return 0;
     38 }
     39 ```
     40 
     41 [1385B - Restore the Permutation by Merger](/contest/1385/problem/B "Codeforces Round 656 (Div. 3)")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 
     52 using namespace std;
     53 
     54 int main() {
     55 #ifdef _DEBUG
     56 	freopen("input.txt", "r", stdin);
     57 //	freopen("output.txt", "w", stdout);
     58 #endif
     59 	
     60 	int t;
     61 	cin >> t;
     62 	while (t--) {
     63 		int n;
     64 		cin >> n;
     65 		vector<int> a(2 * n);
     66 		for (auto &it : a) cin >> it;
     67 		vector<int> used(n);
     68 		vector<int> p;
     69 		for (int i = 0; i < 2 * n; ++i) {
     70 			if (!used[a[i] - 1]) {
     71 				used[a[i] - 1] = true;
     72 				p.push_back(a[i]);
     73 			}
     74 		}
     75 		for (auto it : p) cout << it << " ";
     76 		cout << endl;
     77 	}
     78 	
     79 	return 0;
     80 }
     81 ```
     82 
     83 [1385C - Make It Good](/contest/1385/problem/C "Codeforces Round 656 (Div. 3)")
     84 
     85 **Tutorial**
     86 
     87 Tutorial is loading...
     88 
     89 **Solution**
     90 
     91 ```
     92 #include <bits/stdc++.h>
     93 
     94 using namespace std;
     95 
     96 int main() {
     97 #ifdef _DEBUG
     98 	freopen("input.txt", "r", stdin);
     99 //	freopen("output.txt", "w", stdout);
    100 #endif
    101 	
    102 	int t;
    103 	cin >> t;
    104 	while (t--) {
    105 		int n;
    106 		cin >> n;
    107 		vector<int> a(n);
    108 		for (auto &it : a) cin >> it;
    109 		int pos = n - 1;
    110 		while (pos > 0 && a[pos - 1] >= a[pos]) --pos;
    111 		while (pos > 0 && a[pos - 1] <= a[pos]) --pos;
    112 		cout << pos << endl;
    113 	}
    114 	
    115 	return 0;
    116 }
    117 ```
    118 
    119 [1385D - a-Good String](/contest/1385/problem/D "Codeforces Round 656 (Div. 3)")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 
    130 using namespace std;
    131 
    132 int calc(const string &s, char c) {
    133 	if (s.size() == 1) {
    134 		return s[0] != c;
    135 	}
    136 	int mid = s.size() / 2;
    137 	int cntl = calc(string(s.begin(), s.begin() + mid), c + 1);
    138 	cntl += s.size() / 2 - count(s.begin() + mid, s.end(), c);
    139 	int cntr = calc(string(s.begin() + mid, s.end()), c + 1);
    140 	cntr += s.size() / 2 - count(s.begin(), s.begin() + mid, c);
    141 	return min(cntl, cntr);
    142 }
    143 
    144 int main() {
    145 #ifdef _DEBUG
    146 	freopen("input.txt", "r", stdin);
    147 //	freopen("output.txt", "w", stdout);
    148 #endif
    149 	
    150 	int t;
    151 	cin >> t;
    152 	while (t--) {
    153 		int n;
    154 		string s;
    155 		cin >> n >> s;
    156 		cout << calc(s, 'a') << endl;
    157 	}
    158 	
    159 	return 0;
    160 }
    161 ```
    162 
    163 [1385E - Directing Edges](/contest/1385/problem/E "Codeforces Round 656 (Div. 3)")
    164 
    165 **Tutorial**
    166 
    167 Tutorial is loading...
    168 
    169 **Solution**
    170 
    171 ```
    172 #include <bits/stdc++.h>
    173 
    174 using namespace std;
    175 
    176 vector<int> ord;
    177 vector<int> used;
    178 vector<vector<int>> g;
    179 
    180 void dfs(int v) {
    181 	used[v] = 1;
    182 	for (auto to : g[v]) {
    183 		if (!used[to]) dfs(to);
    184 	}
    185 	ord.push_back(v);
    186 }
    187 
    188 int main() {
    189 #ifdef _DEBUG
    190 	freopen("input.txt", "r", stdin);
    191 //	freopen("output.txt", "w", stdout);
    192 #endif
    193 	
    194 	int t;
    195 	cin >> t;
    196 	while (t--) {
    197 		int n, m;
    198 		cin >> n >> m;
    199 		g = vector<vector<int>>(n);
    200 		vector<pair<int, int>> edges;
    201 		for (int i = 0; i < m; ++i) {
    202 			int t, x, y;
    203 			cin >> t >> x >> y;
    204 			--x, --y;
    205 			if (t == 1) {
    206 				g[x].push_back(y);
    207 			}
    208 			edges.push_back({x, y});
    209 		}
    210 		
    211 		ord.clear();
    212 		used = vector<int>(n);
    213 		for (int i = 0; i < n; ++i) {
    214 			if (!used[i]) dfs(i);
    215 		}
    216 		vector<int> pos(n);
    217 		reverse(ord.begin(), ord.end());
    218 		for (int i = 0; i < n; ++i) {
    219 			pos[ord[i]] = i;
    220 		}
    221 		bool bad = false;
    222 		for (int i = 0; i < n; ++i) {
    223 			for (auto j : g[i]) {
    224 				if (pos[i] > pos[j]) bad = true;
    225 			}
    226 		}
    227 		if (bad) {
    228 			cout << "NO" << endl;
    229 		} else {
    230 			cout << "YES" << endl;
    231 			for (auto [x, y] : edges) {
    232 				if (pos[x] < pos[y]) {
    233 					cout << x + 1 << " " << y + 1 << endl;
    234 				} else {
    235 					cout << y + 1 << " " << x + 1 << endl;
    236 				}
    237 			}
    238 		}
    239 	}
    240 	
    241 	return 0;
    242 }
    243 ```
    244 
    245 [1385F - Removing Leaves](/contest/1385/problem/F "Codeforces Round 656 (Div. 3)")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution**
    252 
    253 ```
    254 #include <bits/stdc++.h>
    255 
    256 using namespace std;
    257 
    258 int n, k, ans;
    259 vector<set<int>> g;
    260 vector<set<int>> leaves;
    261 
    262 struct comp {
    263 	bool operator() (int a, int b) const {
    264 		if (leaves[a].size() == leaves[b].size()) return a < b;
    265 		return leaves[a].size() > leaves[b].size();
    266 	}
    267 };
    268 
    269 int main() {
    270 #ifdef _DEBUG
    271 	freopen("input.txt", "r", stdin);
    272 //	freopen("output.txt", "w", stdout);
    273 #endif
    274 	
    275 	int t;
    276 	cin >> t;
    277 	while (t--) {
    278 		cin >> n >> k;
    279 		g = leaves = vector<set<int>>(n);
    280 		for (int i = 0; i < n - 1; ++i) {
    281 			int x, y;
    282 			cin >> x >> y;
    283 			--x, --y;
    284 			g[x].insert(y);
    285 			g[y].insert(x);
    286 		}
    287 		for (int i = 0; i < n; ++i) {
    288 			if (g[i].size() == 1) {
    289 				leaves[*g[i].begin()].insert(i);
    290 			}
    291 		}
    292 		set<int, comp> st;
    293 		for (int i = 0; i < n; ++i) {
    294 			st.insert(i);
    295 		}
    296 		int ans = 0;
    297 		while (true) {
    298 			int v = *st.begin();
    299 			if (int(leaves[v].size()) < k) break;
    300 			for (int i = 0; i < k; ++i) {
    301 				int leaf = *leaves[v].begin();
    302 				g[leaf].erase(v);
    303 				g[v].erase(leaf);
    304 				st.erase(v);
    305 				st.erase(leaf);
    306 				leaves[v].erase(leaf);
    307 				if (leaves[leaf].count(v)) leaves[leaf].erase(v);
    308 				if (g[v].size() == 1) {
    309 					int to = *g[v].begin();
    310 					st.erase(to);
    311 					leaves[to].insert(v);
    312 					st.insert(to);
    313 				}
    314 				st.insert(v);
    315 				st.insert(leaf);
    316 				
    317 			}
    318 			ans += 1;
    319 		}
    320 		cout << ans << endl;
    321 	}
    322 	
    323 	return 0;
    324 }
    325 ```
    326 
    327 [1385G - Columns Swaps](/contest/1385/problem/G "Codeforces Round 656 (Div. 3)")
    328 
    329 **Tutorial**
    330 
    331 Tutorial is loading...
    332 
    333 **Solution**
    334 
    335 ```
    336 #include <bits/stdc++.h>
    337 
    338 using namespace std;
    339 
    340 int cnt0, cnt1;
    341 vector<int> col, comp;
    342 vector<vector<pair<int, int>>> g;
    343 
    344 void dfs(int v, int c, int cmp) {
    345 	col[v] = c;
    346 	if (col[v] == 0) ++cnt0;
    347 	else ++cnt1;
    348 	comp[v] = cmp;
    349 	for (auto [to, change] : g[v]) {
    350 		if (col[to] == -1) {
    351 			dfs(to, c ^ change, cmp);
    352 		}
    353 	}
    354 }
    355 
    356 int main() {
    357 #ifdef _DEBUG
    358 	freopen("input.txt", "r", stdin);
    359 //	freopen("output.txt", "w", stdout);
    360 #endif
    361 	
    362 	int t;
    363 	cin >> t;
    364 	while (t--) {
    365 		int n;
    366 		cin >> n;
    367 		vector<vector<int>> a(2, vector<int>(n));
    368 		vector<vector<int>> pos(n);
    369 		for (int i = 0; i < 2; ++i) {
    370 			for (int j = 0; j < n; ++j) {
    371 				cin >> a[i][j];
    372 				--a[i][j];
    373 				pos[a[i][j]].push_back(j);
    374 			}
    375 		}
    376 		bool bad = false;
    377 		g = vector<vector<pair<int, int>>>(n);
    378 		for (int i = 0; i < n; ++i) {
    379 			if (pos[i].size() != 2) {
    380 				bad = true;
    381 				break;
    382 			}
    383 			int c1 = pos[i][0], c2 = pos[i][1];
    384 			if (c1 == c2) continue;
    385 			int r1 = a[0][c1] != i, r2 = a[0][c2] != i;
    386 			g[c1].push_back({c2, r1 == r2});
    387 			g[c2].push_back({c1, r1 == r2});
    388 		}
    389 		col = comp = vector<int>(n, -1);
    390 		int cnt = 0;
    391 		vector<pair<int, int>> colcnt;
    392 		int ans = 0;
    393 		for (int i = 0; i < n; ++i) {
    394 			if (col[i] == -1) {
    395 				cnt0 = cnt1 = 0;
    396 				dfs(i, 0, cnt);
    397 				++cnt;
    398 				colcnt.push_back({cnt0, cnt1});
    399 				ans += min(cnt0, cnt1);
    400 			}
    401 		}
    402 		for (int i = 0; i < n; ++i) {
    403 			for (auto [j, diff] : g[i]) {
    404 				if ((col[i] ^ col[j]) != diff) {
    405 					bad = true;
    406 				}
    407 			}
    408 		}
    409 		if (bad) {
    410 			cout << -1 << endl;
    411 		} else {
    412 			cout << ans << endl;
    413 			for (int i = 0; i < n; ++i) {
    414 				int changeZero = colcnt[comp[i]].first < colcnt[comp[i]].second;
    415 				if (col[i] ^ changeZero) {
    416 					cout << i + 1 << " ";
    417 				}
    418 			}
    419 			cout << endl;
    420 		}
    421 	}
    422 	
    423 	return 0;
    424 }
    425 ```