1311.md (7750B)
1 Source: https://codeforces.com/blog/entry/74224 2 3 [1311A - Add Odd or Subtract Even](/contest/1311/problem/A "Codeforces Round 624 (Div. 3)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 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 int a, b; 28 cin >> a >> b; 29 if (a == b) cout << 0 << endl; 30 else cout << 1 + int((a < b) ^ ((b - a) & 1)) << endl; 31 } 32 33 return 0; 34 } 35 ``` 36 37 [1311B - WeirdSort](/contest/1311/problem/B "Codeforces Round 624 (Div. 3)") 38 39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (n^2)** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 int main() { 53 #ifdef _DEBUG 54 freopen("input.txt", "r", stdin); 55 // freopen("output.txt", "w", stdout); 56 #endif 57 58 int t; 59 cin >> t; 60 while (t--) { 61 int n, m; 62 cin >> n >> m; 63 vector<int> a(n); 64 for (int i = 0; i < n; ++i) { 65 cin >> a[i]; 66 } 67 vector<int> p(n); 68 for (int i = 0; i < m; ++i) { 69 int pos; 70 cin >> pos; 71 p[pos - 1] = 1; 72 } 73 while (true) { 74 bool ok = false; 75 for (int i = 0; i < n; ++i) { 76 if (p[i] && a[i] > a[i + 1]) { 77 ok = true; 78 swap(a[i], a[i + 1]); 79 } 80 } 81 if (!ok) break; 82 } 83 bool ok = true; 84 for (int i = 0; i < n - 1; ++i) { 85 ok &= a[i] <= a[i + 1]; 86 } 87 if (ok) cout << "YES" << endl; 88 else cout << "NO" << endl; 89 } 90 91 return 0; 92 } 93 ``` 94 95 **Solution (n log n)** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 int main() { 103 #ifdef _DEBUG 104 freopen("input.txt", "r", stdin); 105 // freopen("output.txt", "w", stdout); 106 #endif 107 108 int t; 109 cin >> t; 110 while (t--) { 111 int n, m; 112 cin >> n >> m; 113 vector<int> a(n); 114 for (int i = 0; i < n; ++i) { 115 cin >> a[i]; 116 } 117 vector<int> p(n); 118 for (int i = 0; i < m; ++i) { 119 int pos; 120 cin >> pos; 121 p[pos - 1] = 1; 122 } 123 for (int i = 0; i < n; ++i) { 124 if (p[i] == 0) continue; 125 int j = i; 126 while (j < n && p[j]) ++j; 127 sort(a.begin() + i, a.begin() + j + 1); 128 i = j; 129 } 130 bool ok = true; 131 for (int i = 0; i < n - 1; ++i) { 132 ok &= a[i] <= a[i + 1]; 133 } 134 if (ok) cout << "YES" << endl; 135 else cout << "NO" << endl; 136 } 137 138 return 0; 139 } 140 ``` 141 142 [1311C - Perform the Combo](/contest/1311/problem/C "Codeforces Round 624 (Div. 3)") 143 144 Idea: [vovuh](/profile/vovuh "Master vovuh") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Solution** 151 152 ``` 153 #include <bits/stdc++.h> 154 155 using namespace std; 156 157 int main() { 158 #ifdef _DEBUG 159 freopen("input.txt", "r", stdin); 160 // freopen("output.txt", "w", stdout); 161 #endif 162 163 int t; 164 cin >> t; 165 while (t--) { 166 int n, m; 167 string s; 168 cin >> n >> m >> s; 169 vector<int> pref(n); 170 for (int i = 0; i < m; ++i) { 171 int p; 172 cin >> p; 173 ++pref[p - 1]; 174 } 175 for (int i = n - 1; i > 0; --i) { 176 pref[i - 1] += pref[i]; 177 } 178 vector<int> ans(26); 179 for (int i = 0; i < n; ++i) { 180 ans[s[i] - 'a'] += pref[i]; 181 ++ans[s[i] - 'a']; 182 } 183 for (int i = 0; i < 26; ++i) { 184 cout << ans[i] << " "; 185 } 186 cout << endl; 187 } 188 189 return 0; 190 } 191 ``` 192 193 [1311D - Three Integers](/contest/1311/problem/D "Codeforces Round 624 (Div. 3)") 194 195 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 196 197 **Tutorial** 198 199 Tutorial is loading... 200 201 **Solution** 202 203 ``` 204 #include <bits/stdc++.h> 205 206 using namespace std; 207 208 int main() { 209 #ifdef _DEBUG 210 freopen("input.txt", "r", stdin); 211 // freopen("output.txt", "w", stdout); 212 #endif 213 214 int t; 215 cin >> t; 216 while (t--) { 217 int a, b, c; 218 cin >> a >> b >> c; 219 int ans = 1e9; 220 int A = -1, B = -1, C = -1; 221 for (int cA = 1; cA <= 2 * a; ++cA) { 222 for (int cB = cA; cB <= 2 * b; cB += cA) { 223 for (int i = 0; i < 2; ++i) { 224 int cC = cB * (c / cB) + i * cB; 225 int res = abs(cA - a) + abs(cB - b) + abs(cC - c); 226 if (ans > res) { 227 ans = res; 228 A = cA; 229 B = cB; 230 C = cC; 231 } 232 } 233 } 234 } 235 cout << ans << endl << A << " " << B << " " << C << endl; 236 } 237 238 return 0; 239 } 240 ``` 241 242 [1311E - Construct the Binary Tree](/contest/1311/problem/E "Codeforces Round 624 (Div. 3)") 243 244 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 245 246 **Tutorial** 247 248 Tutorial is loading... 249 250 **Solution** 251 252 ``` 253 #include <bits/stdc++.h> 254 255 using namespace std; 256 257 int main() { 258 #ifdef _DEBUG 259 freopen("input.txt", "r", stdin); 260 // freopen("output.txt", "w", stdout); 261 #endif 262 263 int t; 264 cin >> t; 265 while (t--) { 266 int n, d; 267 cin >> n >> d; 268 int ld = 0, rd = n * (n - 1) / 2; 269 for (int i = 1, cd = 0; i <= n; ++i) { 270 if (!(i & (i - 1))) ++cd; 271 ld += cd - 1; 272 } 273 if (!(ld <= d && d <= rd)) { 274 cout << "NO" << endl; 275 continue; 276 } 277 278 vector<int> par(n); 279 iota(par.begin(), par.end(), -1); 280 281 vector<int> cnt(n, 1); 282 cnt[n - 1] = 0; 283 284 vector<int> bad(n); 285 286 vector<int> dep(n); 287 iota(dep.begin(), dep.end(), 0); 288 289 int cur = n * (n - 1) / 2; 290 while (cur > d) { 291 int v = -1; 292 for (int i = 0; i < n; ++i) { 293 if (!bad[i] && cnt[i] == 0 && (v == -1 || dep[v] > dep[i])) { 294 v = i; 295 } 296 } 297 assert(v != -1); 298 int p = -1; 299 for (int i = 0; i < n; ++i) { 300 if (cnt[i] < 2 && dep[i] < dep[v] - 1 && (p == -1 || dep[p] < dep[i])) { 301 p = i; 302 } 303 } 304 if (p == -1) { 305 bad[v] = 1; 306 continue; 307 } 308 assert(dep[v] - dep[p] == 2); 309 --cnt[par[v]]; 310 --dep[v]; 311 ++cnt[p]; 312 par[v] = p; 313 --cur; 314 } 315 316 cout << "YES" << endl; 317 for (int i = 1; i < n; ++i) cout << par[i] + 1 << " "; 318 cout << endl; 319 } 320 321 return 0; 322 } 323 ``` 324 325 [1311F - Moving Points](/contest/1311/problem/F "Codeforces Round 624 (Div. 3)") 326 327 Idea: [vovuh](/profile/vovuh "Master vovuh") 328 329 **Tutorial** 330 331 Tutorial is loading... 332 333 **Solution (Fenwick tree)** 334 335 ``` 336 #include <bits/stdc++.h> 337 338 using namespace std; 339 340 long long get(vector<long long> &f, int pos) { 341 long long res = 0; 342 for (; pos >= 0; pos = (pos & (pos + 1)) - 1) 343 res += f[pos]; 344 return res; 345 } 346 347 void upd(vector<long long> &f, int pos, int val) { 348 for (; pos < int(f.size()); pos |= pos + 1) { 349 f[pos] += val; 350 } 351 } 352 353 int main() { 354 #ifdef _DEBUG 355 freopen("input.txt", "r", stdin); 356 // freopen("output.txt", "w", stdout); 357 #endif 358 359 int n; 360 cin >> n; 361 vector<pair<int, int>> p(n); 362 for (auto &pnt : p) cin >> pnt.first; 363 for (auto &pnt : p) cin >> pnt.second; 364 sort(p.begin(), p.end()); 365 366 vector<int> vs; 367 for (auto &pnt : p) vs.push_back(pnt.second); 368 sort(vs.begin(), vs.end()); 369 vs.resize(unique(vs.begin(), vs.end()) - vs.begin()); 370 371 long long ans = 0; 372 vector<long long> cnt(vs.size()), xs(vs.size()); 373 for (auto &pnt : p) { 374 int pos = lower_bound(vs.begin(), vs.end(), pnt.second) - vs.begin(); 375 ans += get(cnt, pos) * 1ll * pnt.first - get(xs, pos); 376 upd(cnt, pos, 1); 377 upd(xs, pos, pnt.first); 378 } 379 380 cout << ans << endl; 381 382 return 0; 383 } 384 ``` 385 386 **Solution (pbds)** 387 388 ``` 389 #include <bits/stdc++.h> 390 #include <ext/pb_ds/tree_policy.hpp> 391 #include <ext/pb_ds/assoc_container.hpp> 392 393 using namespace std; 394 using namespace __gnu_pbds; 395 396 typedef 397 tree< 398 pair<int, int>, 399 null_type, 400 less<pair<int, int>>, 401 rb_tree_tag, 402 tree_order_statistics_node_update> 403 ordered_set; 404 405 int main() { 406 #ifdef _DEBUG 407 freopen("input.txt", "r", stdin); 408 // freopen("output.txt", "w", stdout); 409 #endif 410 411 int n; 412 cin >> n; 413 vector<pair<int, int>> p(n); 414 for (auto &pnt : p) cin >> pnt.first; 415 for (auto &pnt : p) cin >> pnt.second; 416 sort(p.begin(), p.end()); 417 418 ordered_set s; 419 long long ans = 0; 420 for (int i = 0; i < n; ++i) { 421 int cnt = s.order_of_key(make_pair(p[i].second + 1, -1)); 422 ans += cnt * 1ll * p[i].first; 423 s.insert(make_pair(p[i].second, i)); 424 } 425 s.clear(); 426 for (int i = n - 1; i >= 0; --i) { 427 int cnt = int(s.size()) - s.order_of_key(make_pair(p[i].second - 1, n)); 428 ans -= cnt * 1ll * p[i].first; 429 s.insert(make_pair(p[i].second, i)); 430 } 431 432 cout << ans << endl; 433 434 return 0; 435 } 436 ```