1472.md (7087B)
1 Source: https://codeforces.com/blog/entry/86406 2 3 All problems were invented [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and developed by me [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz") and [Stepavly](/profile/Stepavly "Master Stepavly"). 4 5 [1472A - Cards for Friends](/contest/1472/problem/A "Codeforces Round 693 (Div. 3)") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 using ll = long long; 18 19 void solve() { 20 int w, h, n; 21 cin >> w >> h >> n; 22 int res = 1; 23 while (w % 2 == 0) { 24 w /= 2; 25 res *= 2; 26 } 27 while (h % 2 == 0) { 28 h /= 2; 29 res *= 2; 30 } 31 cout << (res >= n ? "YES\n" : "NO\n"); 32 } 33 34 int main() { 35 int t; 36 cin >> t; 37 while (t--) { 38 solve(); 39 } 40 } 41 ``` 42 43 [1472B - Fair Division](/contest/1472/problem/B "Codeforces Round 693 (Div. 3)") 44 45 **Editorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 using ll = long long; 56 57 void solve() { 58 int n; 59 cin >> n; 60 int cnt1 = 0, cnt2 = 0; 61 for (int i = 0; i < n; i++) { 62 int c; 63 cin >> c; 64 if (c == 1) { 65 cnt1++; 66 } else { 67 cnt2++; 68 } 69 } 70 if ((cnt1 + 2 * cnt2) % 2 != 0) { 71 cout << "NO\n"; 72 } else { 73 int sum = (cnt1 + 2 * cnt2) / 2; 74 if (sum % 2 == 0 || (sum % 2 == 1 && cnt1 != 0)) { 75 cout << "YES\n"; 76 } else { 77 cout << "NO\n"; 78 } 79 } 80 } 81 82 int main() { 83 int t; 84 cin >> t; 85 while (t--) { 86 solve(); 87 } 88 } 89 ``` 90 91 [1472C - Long Jumps](/contest/1472/problem/C "Codeforces Round 693 (Div. 3)") 92 93 **Editorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 #include <bits/stdc++.h> 101 using namespace std; 102 103 void solve() { 104 int n; 105 cin >> n; 106 vector<int> a(n); 107 for (int &x : a) { 108 cin >> x; 109 } 110 111 vector<int> dp(n); 112 for (int i = n - 1; i >= 0; i--) { 113 dp[i] = a[i]; 114 int j = i + a[i]; 115 if (j < n) { 116 dp[i] += dp[j]; 117 } 118 } 119 cout << *max_element(dp.begin(), dp.end()) << endl; 120 } 121 122 int main() { 123 int tests; 124 cin >> tests; 125 while (tests-- > 0) { 126 solve(); 127 } 128 return 0; 129 } 130 ``` 131 132 [1472D - Even-Odd Game](/contest/1472/problem/D "Codeforces Round 693 (Div. 3)") 133 134 **Editorial** 135 136 Tutorial is loading... 137 138 **Solution** 139 140 ``` 141 #include <bits/stdc++.h> 142 143 using namespace std; 144 using ll = long long; 145 146 void solve() { 147 int n; 148 cin >> n; 149 vector<int> v(n); 150 for (int &e : v) { 151 cin >> e; 152 } 153 sort(v.rbegin(), v.rend()); 154 ll ans = 0; 155 for (int i = 0; i < n; i++) { 156 if (i % 2 == 0) { 157 if (v[i] % 2 == 0) { 158 ans += v[i]; 159 } 160 } else { 161 if (v[i] % 2 == 1) { 162 ans -= v[i]; 163 } 164 } 165 } 166 if (ans == 0) { 167 cout << "Tie\n"; 168 } else if (ans > 0) { 169 cout << "Alice\n"; 170 } else { 171 cout << "Bob\n"; 172 } 173 } 174 175 int main() { 176 int t; 177 cin >> t; 178 while (t--) { 179 solve(); 180 } 181 return 0; 182 } 183 ``` 184 185 [1472E - Correct Placement](/contest/1472/problem/E "Codeforces Round 693 (Div. 3)") 186 187 **Editorial** 188 189 Tutorial is loading... 190 191 **Solution** 192 193 ``` 194 #include <bits/stdc++.h> 195 using namespace std; 196 197 using pii = pair<int, int>; 198 199 struct man { 200 int h, w, id; 201 }; 202 203 bool operator<(const man &a, const man &b) { 204 return tie(a.h, a.w, a.id) < tie(b.h, b.w, b.id); 205 } 206 207 struct my_min { 208 pii mn1, mn2; 209 }; 210 211 vector<pair<int, my_min>> createPrefMins(const vector<man>& a) { 212 vector<pair<int, my_min>> prefMin; 213 my_min curMin{pii(INT_MAX, -1), pii(INT_MAX, -1)}; 214 for (auto x : a) { 215 if (x.w < curMin.mn1.first) { 216 curMin.mn2 = curMin.mn1; 217 curMin.mn1 = pii(x.w, x.id); 218 } else { 219 curMin.mn2 = min(curMin.mn2, pii(x.w, x.id)); 220 } 221 prefMin.emplace_back(x.h, curMin); 222 } 223 return prefMin; 224 } 225 226 int findAny(const vector<pair<int, my_min>> &mins, int h, int w, int id) { 227 int l = -1, r = (int) mins.size(); 228 while (r - l > 1) { 229 int m = (l + r) / 2; 230 if (mins[m].first < h) { 231 l = m; 232 } else { 233 r = m; 234 } 235 } 236 if (l == -1) { 237 return -1; 238 } 239 240 auto mn1 = mins[l].second.mn1; 241 auto mn2 = mins[l].second.mn2; 242 if (mn1.second != id) { 243 return mn1.first < w ? mn1.second + 1 : -1; 244 } 245 return mn2.first < w ? mn2.second + 1 : -1; 246 } 247 248 void solve() { 249 int n; 250 cin >> n; 251 vector<man> hor, ver; 252 vector<pii> a; 253 for (int i = 0; i < n; i++) { 254 int h, w; 255 cin >> h >> w; 256 hor.push_back({h, w, i}); 257 ver.push_back({w, h, i}); 258 a.emplace_back(h, w); 259 } 260 261 sort(hor.begin(), hor.end()); 262 sort(ver.begin(), ver.end()); 263 264 auto horMins = createPrefMins(hor); 265 auto verMins = createPrefMins(ver); 266 267 for (int i = 0; i < n; i++) { 268 auto[h, w] = a[i]; 269 int id = findAny(horMins, h, w, i); 270 if (id == -1) { 271 id = findAny(verMins, h, w, i); 272 } 273 cout << id << " "; 274 } 275 cout << endl; 276 } 277 278 int main() { 279 int tests; 280 cin >> tests; 281 while (tests-- > 0) { 282 solve(); 283 } 284 return 0; 285 } 286 ``` 287 288 [1472F - New Year's Puzzle](/contest/1472/problem/F "Codeforces Round 693 (Div. 3)") 289 290 **Editorial** 291 292 Tutorial is loading... 293 294 **Solution** 295 296 ``` 297 #include <bits/stdc++.h> 298 299 using namespace std; 300 using ll = long long; 301 302 void solve() { 303 int n, m; 304 cin >> n >> m; 305 map<int, int> v; 306 for (int i = 0; i < m; i++) { 307 int x, y; 308 cin >> x >> y; 309 v[y] |= (1 << (x - 1)); 310 } 311 const int FULL = 3; 312 v[2e9] = FULL; 313 int hasLast = 0, lastColor = 0; 314 for (auto[x, mask] : v) { 315 if (mask != FULL && hasLast) { 316 int color = (x + mask) % 2; 317 if (lastColor == color) { 318 cout << "NO\n"; 319 return; 320 } else { 321 hasLast = false; 322 } 323 } else if (mask == FULL && hasLast) { 324 cout << "NO\n"; 325 return; 326 } else if (mask != FULL) { 327 lastColor = (x + mask) % 2; 328 hasLast = true; 329 } 330 } 331 cout << "YES\n"; 332 } 333 334 int main() { 335 int t; 336 cin >> t; 337 while (t--) { 338 solve(); 339 } 340 return 0; 341 } 342 ``` 343 344 [1472G - Moving to the Capital](/contest/1472/problem/G "Codeforces Round 693 (Div. 3)") 345 346 **Editorial** 347 348 Tutorial is loading... 349 350 **Solution** 351 352 ``` 353 #include <bits/stdc++.h> 354 using namespace std; 355 356 vector<int> calcDist(vector<vector<int>> const &g) { 357 vector<int> dist(g.size(), -1); 358 dist[1] = 0; 359 queue<int> pq; 360 pq.push(1); 361 while (!pq.empty()) { 362 int u = pq.front(); 363 pq.pop(); 364 for (int v : g[u]) { 365 if (dist[v] == -1) { 366 dist[v] = dist[u] + 1; 367 pq.push(v); 368 } 369 } 370 } 371 372 return dist; 373 } 374 375 void dfs(int u, vector<vector<int>> const &g, vector<int> const &dist, vector<int> &dp, vector<bool> &used) { 376 used[u] = true; 377 dp[u] = dist[u]; 378 for (int v : g[u]) { 379 if (!used[v] && dist[u] < dist[v]) { 380 dfs(v, g, dist, dp, used); 381 } 382 383 if (dist[u] < dist[v]) { 384 dp[u] = min(dp[u], dp[v]); 385 } else { 386 dp[u] = min(dp[u], dist[v]); 387 } 388 } 389 } 390 391 void solve() { 392 int n, m; 393 cin >> n >> m; 394 vector<vector<int>> g(n + 1); 395 for (int i = 0; i < m; i++) { 396 int u, v; 397 cin >> u >> v; 398 g[u].push_back(v); 399 } 400 401 vector<int> dist = calcDist(g); 402 vector<int> dp(n + 1); 403 vector<bool> used(n + 1); 404 dfs(1, g, dist, dp, used); 405 for (int i = 1; i <= n; i++) { 406 cout << dp[i] << " "; 407 } 408 cout << endl; 409 } 410 411 int main() { 412 int tests; 413 cin >> tests; 414 while (tests-- > 0) { 415 solve(); 416 } 417 return 0; 418 } 419 ```