2110.md (7809B)
1 Source: https://codeforces.com/blog/entry/143186 2 3 I hope everyone enjoyed the tasks, and thank you for participating. 4 5 [2110A - Fashionable Array](/contest/2110/problem/A "Codeforces Round 1026 (Div. 2)") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 void solve() { 19 int n; 20 cin >> n; 21 vector<int> x(n); 22 for (int i = 0; i < n; ++i) { 23 cin >> x[i]; 24 } 25 sort(x.begin(), x.end()); 26 if (x[0] % 2 == x[n - 1] % 2) { 27 cout << 0 << endl; 28 return; 29 } 30 int left = n, right = n; 31 for (int i = 1; i < n; ++i) { 32 if (x[i] % 2 != x[0] % 2) { 33 left = i; 34 break; 35 } 36 } 37 for (int i = 1; i < n; ++i) { 38 if (x[n - i - 1] % 2 != x[n - 1] % 2) { 39 right = i; 40 break; 41 } 42 } 43 cout << min(left, right) << '\n'; 44 } 45 46 int main() { 47 int t; 48 cin >> t; 49 while (t--) { 50 solve(); 51 } 52 } 53 ``` 54 55 [2110B - Down with Brackets](/contest/2110/problem/B "Codeforces Round 1026 (Div. 2)") 56 57 **Editorial** 58 59 Tutorial is loading... 60 61 **Solution** 62 63 ``` 64 #include "bits/stdc++.h" 65 #define int long long 66 #define all(v) (v).begin(), (v).end() 67 #define pb push_back 68 #define em emplace_back 69 #define mp make_pair 70 #define F first 71 #define S second 72 73 using namespace std; 74 template<class C> 75 using vec = vector<C>; 76 using vi = vector<int>; 77 using vpi = vector<pair<int, int>>; 78 using pii = pair<int, int>; 79 80 void solve() { 81 string s; 82 cin >> s; 83 int n = s.size(); 84 int bal = 0; 85 for (int i = 1; i + 1 < n; i++) { 86 if (s[i] == '(') bal++; 87 else bal--; 88 if (bal < 0) { 89 cout << "YES\n"; 90 return; 91 } 92 } 93 if (bal == 0) { 94 cout << "NO\n"; 95 } else { 96 cout << "YES\n"; 97 } 98 } 99 100 signed main() { 101 int tt; 102 cin >> tt; 103 while (tt--) { 104 solve(); 105 } 106 } 107 ``` 108 109 [2110C - Racing](/contest/2110/problem/C "Codeforces Round 1026 (Div. 2)") 110 111 **Editorial** 112 113 Tutorial is loading... 114 115 **Solution** 116 117 ``` 118 #include <bits/stdc++.h> 119 120 using namespace std; 121 122 void solve() { 123 int n; 124 cin >> n; 125 vector<int> d(n); 126 for (auto &x : d) { 127 cin >> x; 128 } 129 vector<int> l(n), r(n); 130 for (int i = 0; i < n; ++i) { 131 cin >> l[i] >> r[i]; 132 } 133 int left = 0; 134 vector<int> last; 135 for (int i = 0; i < n; ++i) { 136 if (d[i] == -1) { 137 last.push_back(i); 138 } else { 139 left += d[i]; 140 } 141 while (left < l[i]) { 142 if (last.empty()) { 143 cout << -1 << '\n'; 144 return; 145 } 146 d[last.back()] = 1; 147 ++left; 148 last.pop_back(); 149 } 150 while (left + last.size() > r[i]) { 151 if (last.empty()) { 152 cout << -1 << '\n'; 153 return; 154 } 155 d[last.back()] = 0; 156 last.pop_back(); 157 } 158 } 159 for (auto &x : d) { 160 cout << max(0, x) << " "; 161 } 162 cout << "\n"; 163 return; 164 } 165 166 signed main() { 167 ios::sync_with_stdio(false); 168 cin.tie(0); 169 int t; 170 cin >> t; 171 while (t--) { 172 solve(); 173 } 174 return 0; 175 } 176 ``` 177 178 [2110D - Fewer Batteries](/contest/2110/problem/D "Codeforces Round 1026 (Div. 2)") 179 180 **Editorial** 181 182 Tutorial is loading... 183 184 **Solution** 185 186 ``` 187 #include <bits/stdc++.h> 188 189 using namespace std; 190 191 const int INF = 1e9 + 11; 192 193 struct edge { 194 int t, w; 195 edge(int t, int w) : t(t), w(w) {} 196 }; 197 198 void solve() { 199 int n, m; 200 cin >> n >> m; 201 vector<int> b(n); 202 for (auto &x : b) { 203 cin >> x; 204 } 205 vector<vector<edge>> graph(n); 206 for (int i = 0; i < m; ++i) { 207 int s, t, w; 208 cin >> s >> t >> w; 209 --s; --t; 210 graph[s].push_back(edge(t, w)); 211 } 212 auto check = [&](int maxW) { 213 vector<int> best(n, 0); 214 for (int i = 0; i < n; ++i) { 215 if (i > 0 && best[i] == 0) { 216 continue; 217 } 218 best[i] += b[i]; 219 best[i] = min(best[i], maxW); 220 for (auto p : graph[i]) { 221 if (p.w <= best[i]) { 222 best[p.t] = max(best[p.t], best[i]); 223 } 224 } 225 } 226 return (best.back() > 0); 227 }; 228 if (!check(INF)) { 229 cout << -1 << endl; 230 return; 231 } 232 int l = 0, r = INF; 233 while (r - l > 1) { 234 int mid = (l + r) / 2; 235 if (check(mid)) { 236 r = mid; 237 } else { 238 l = mid; 239 } 240 } 241 cout << r << endl; 242 } 243 244 int main() { 245 ios::sync_with_stdio(false); 246 cin.tie(0); 247 int t; 248 cin >> t; 249 while (t--) { 250 solve(); 251 } 252 return 0; 253 } 254 ``` 255 256 [2110E - Melody](/contest/2110/problem/E "Codeforces Round 1026 (Div. 2)") 257 258 **Editorial** 259 260 Tutorial is loading... 261 262 **Solution** 263 264 ``` 265 #include <bits/stdc++.h> 266 267 using namespace std; 268 269 vector<set<int>> graph; 270 vector<int> ans; 271 272 void dfs(int v) { 273 while (!graph[v].empty()) { 274 int u = *graph[v].begin(); 275 graph[u].erase(v); 276 graph[v].erase(u); 277 dfs(u); 278 } 279 ans.push_back(v); 280 } 281 282 signed main() { 283 int t; 284 cin >> t; 285 while (t--) { 286 graph.clear(); 287 ans.clear(); 288 int n; 289 cin >> n; 290 map<int, int> p, v; 291 map<pair<int, int>, int> toIndex; 292 vector<pair<int, int>> part; 293 for (int i = 1; i <= n; ++i) { 294 int volume, pitch; 295 cin >> volume >> pitch; 296 toIndex[make_pair(volume, pitch)] = i; 297 if (p.count(pitch) == 0) { 298 p[pitch] = graph.size(); 299 graph.push_back(set<int>()); 300 part.push_back(make_pair(0, pitch)); 301 } 302 if (v.count(volume) == 0) { 303 v[volume] = graph.size(); 304 graph.push_back(set<int>()); 305 part.push_back(make_pair(volume, 0)); 306 } 307 graph[v[volume]].insert(p[pitch]); 308 graph[p[pitch]].insert(v[volume]); 309 } 310 int root = 0; 311 int cnt = 0; 312 for (int i = 0; i < graph.size(); ++i) { 313 if (graph[i].size() % 2 == 1) { 314 ++cnt; 315 root = i; 316 } 317 } 318 dfs(root); 319 if (ans.size() != n + 1 || cnt > 2) { 320 cout << "NO" << endl; 321 continue; 322 } 323 vector<int> out; 324 for (int i = 0; i < n; ++i) { 325 auto p1 = part[ans[i]]; 326 auto p2 = part[ans[i + 1]]; 327 out.push_back(toIndex[make_pair(p1.first + p2.first, p1.second + p2.second)]); 328 if (out[i] == 0) { 329 out.clear(); 330 break; 331 } 332 } 333 if (out.empty()) { 334 cout << "NO" << endl; 335 } else { 336 cout << "YES" << endl; 337 for (int i = 0; i < n; ++i) { 338 cout << out[i] << " "; 339 } 340 cout << endl; 341 } 342 } 343 return 0; 344 } 345 ``` 346 347 [2110F - Faculty](/contest/2110/problem/F "Codeforces Round 1026 (Div. 2)") 348 349 **Editorial** 350 351 Tutorial is loading... 352 353 **Solution** 354 355 ``` 356 #include <bits/stdc++.h> 357 358 using namespace std; 359 360 int f(int x, int y) { 361 return (x % y) + (y % x); 362 } 363 364 void Solve() { 365 int n; 366 cin >> n; 367 vector<int> a(n); 368 for (int i = 0; i < n; ++i) { 369 cin >> a[i]; 370 } 371 int ans = 0; 372 int mx = a[0]; 373 for (int i = 0; i < n; ++i) { 374 ans = max(ans, f(mx, a[i])); 375 if (a[i] > mx) { 376 if (a[i] >= mx * 2) { 377 mx = a[i]; 378 for (int j = 0; j < i; ++j) { 379 ans = max(ans, f(a[i], a[j])); 380 } 381 } else { 382 mx = a[i]; 383 ans = mx; 384 } 385 } 386 cout << ans << ' '; 387 } 388 cout << endl; 389 } 390 391 int main() { 392 ios::sync_with_stdio(false); 393 cin.tie(0); 394 int t; 395 cin >> t; 396 while (t--) { 397 Solve(); 398 } 399 return 0; 400 } 401 ```