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 ```