1535.md (9703B)
1 Source: https://codeforces.com/blog/entry/91481 2 3 [1535A - Fair Playoff](/contest/1535/problem/A "Educational Codeforces Round 110 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 vector<int> s(4); 23 for (int& x : s) cin >> x; 24 if (min(s[0], s[1]) > max(s[2], s[3]) || max(s[0], s[1]) < min(s[2], s[3])) 25 cout << "NO\n"; 26 else 27 cout << "YES\n"; 28 } 29 } 30 ``` 31 32 [1535B - Array Reodering](/contest/1535/problem/B "Educational Codeforces Round 110 (Rated for Div. 2)") 33 34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (Neon)** 41 42 ``` 43 #include <bits/stdc++.h> 44 45 using namespace std; 46 47 int main() { 48 int t; 49 cin >> t; 50 while (t--) { 51 int n; 52 cin >> n; 53 vector<int> a(n); 54 for (int &x : a) cin >> x; 55 sort(a.begin(), a.end(), [](int x, int y) { 56 return x % 2 < y % 2; 57 }); 58 int ans = 0; 59 for (int i = 0; i < n; ++i) { 60 for (int j = i + 1; j < n; ++j) { 61 ans += __gcd(a[i], a[j] * 2) > 1; 62 } 63 } 64 cout << ans << endl; 65 } 66 } 67 ``` 68 69 [1535C - Unstable String](/contest/1535/problem/C "Educational Codeforces Round 110 (Rated for Div. 2)") 70 71 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 72 73 **Tutorial** 74 75 Tutorial is loading... 76 77 **Solution (Neon)** 78 79 ``` 80 #include <bits/stdc++.h> 81 82 using namespace std; 83 84 int main() { 85 int t; 86 cin >> t; 87 while (t--) { 88 string s; 89 cin >> s; 90 vector<vector<int>> lst(2, vector<int>(2, -1)); 91 long long ans = 0; 92 for (int i = 0; i < int(s.size()); ++i) { 93 int j = i - 1; 94 int p = i & 1; 95 if (s[i] != '1') j = min(j, max(lst[0][p ^ 1], lst[1][p])); 96 if (s[i] != '0') j = min(j, max(lst[0][p], lst[1][p ^ 1])); 97 ans += i - j; 98 if (s[i] != '?') lst[s[i] - '0'][p] = i; 99 } 100 cout << ans << '\n'; 101 } 102 } 103 ``` 104 105 [1535D - Playoff Tournament](/contest/1535/problem/D "Educational Codeforces Round 110 (Rated for Div. 2)") 106 107 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 108 109 **Tutorial** 110 111 Tutorial is loading... 112 113 **Solution (Neon)** 114 115 ``` 116 #include <bits/stdc++.h> 117 118 using namespace std; 119 120 int main() { 121 ios_base::sync_with_stdio(false); 122 cin.tie(NULL); 123 124 int k; 125 cin >> k; 126 string s; 127 cin >> s; 128 reverse(s.begin(), s.end()); 129 130 int n = 1 << k; 131 vector<int> cnt(2 * n, 1); 132 133 auto upd = [&](int i) { 134 return cnt[i] = (s[i] != '0' ? cnt[i * 2 + 1] : 0) + (s[i] != '1' ? cnt[i * 2 + 2] : 0); 135 }; 136 137 for (int i = n - 2; i >= 0; i--) { 138 upd(i); 139 } 140 141 int q; 142 cin >> q; 143 while (q--) { 144 int p; 145 char c; 146 cin >> p >> c; 147 p = n - p - 1; 148 s[p] = c; 149 while (p) { 150 upd(p); 151 p = (p - 1) / 2; 152 } 153 cout << upd(0) << '\n'; 154 } 155 } 156 ``` 157 158 [1535E - Gold Transfer](/contest/1535/problem/E "Educational Codeforces Round 110 (Rated for Div. 2)") 159 160 Idea: [adedalic](/profile/adedalic "International Master adedalic") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution (adedalic)** 167 168 ``` 169 #include<bits/stdc++.h> 170 171 using namespace std; 172 173 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 174 #define sz(a) int((a).size()) 175 176 #define x first 177 #define y second 178 179 typedef long long li; 180 typedef pair<int, int> pt; 181 182 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 183 return out << "(" << p.x << ", " << p.y << ")"; 184 } 185 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 186 out << "["; 187 fore(i, 0, sz(v)) { 188 if(i) out << ", "; 189 out << v[i]; 190 } 191 return out << "]"; 192 } 193 194 const int INF = int(1e9); 195 const li INF64 = li(1e18); 196 197 const int LOG = 20; 198 199 int q; 200 vector<int> a, c; 201 vector<int> p[LOG]; 202 203 int main() { 204 cin >> q; 205 a.resize(q + 1); 206 c.resize(q + 1); 207 208 fore (lg, 0, LOG) 209 p[lg].resize(q + 1); 210 211 fore (lg, 0, LOG) 212 p[lg][0] = 0; 213 cin >> a[0] >> c[0]; 214 215 fore (id, 1, q + 1) { 216 int tp; cin >> tp; 217 if (tp == 1) { 218 int pr; cin >> pr; 219 cin >> a[id] >> c[id]; 220 221 p[0][id] = pr; 222 fore (lg, 1, LOG) 223 p[lg][id] = p[lg - 1][p[lg - 1][id]]; 224 } 225 else { 226 int v, w; 227 cin >> v >> w; 228 229 int ansR = 0; 230 li ansS = 0; 231 232 while (w > 0 && a[v] > 0) { 233 int u = v; 234 for (int lg = LOG - 1; lg >= 0; lg--) { 235 if (a[p[lg][u]] > 0) 236 u = p[lg][u]; 237 } 238 int mn = min(a[u], w); 239 a[u] -= mn; 240 w -= mn; 241 242 ansR += mn; 243 ansS += mn * 1ll * c[u]; 244 } 245 cout << ansR << " " << ansS << endl; 246 } 247 } 248 249 return 0; 250 } 251 ``` 252 253 [1535F - String Distance](/contest/1535/problem/F "Educational Codeforces Round 110 (Rated for Div. 2)") 254 255 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 256 257 **Tutorial** 258 259 Tutorial is loading... 260 261 **Solution (BledDest)** 262 263 ``` 264 #include<bits/stdc++.h> 265 using namespace std; 266 267 const int LN = 20; 268 const int K = 12000; 269 270 int pw2[1 << LN]; 271 272 vector<int> sorted_segments(const string& s) 273 { 274 int n = int(s.size()) - 1; 275 vector<int> res(n); 276 for(int i = 0; i < n; i++) 277 if(s[i] <= s[i + 1]) 278 res[i] = 0; 279 else 280 res[i] = 1; 281 return res; 282 } 283 284 vector<int> prefix_sum(const vector<int>& s) 285 { 286 int n = s.size(); 287 vector<int> p(n + 1); 288 for(int i = 0; i < n; i++) 289 p[i + 1] = p[i] + s[i]; 290 return p; 291 } 292 293 int naiveLCP(const string& s, const string& t) 294 { 295 int ans = 0; 296 int n = s.size(); 297 int m = t.size(); 298 while(ans < n && ans < m && s[ans] == t[ans]) 299 ans++; 300 return ans; 301 } 302 303 vector<vector<int>> build_table(const vector<int>& a) 304 { 305 int n = a.size(); 306 vector<vector<int>> table(LN, vector<int>(n)); 307 for(int i = 0; i < n; i++) 308 table[0][i] = a[i]; 309 for(int i = 1; i < LN; i++) 310 for(int j = 0; j < n; j++) 311 if(j + (1 << (i - 1)) < n) 312 table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); 313 else 314 table[i][j] = table[i - 1][j]; 315 return table; 316 } 317 318 struct LCP 319 { 320 vector<int> idx; 321 vector<vector<int>> table; 322 323 int query_inner(int x, int y) 324 { 325 if(x > y) swap(x, y); 326 int len = y - x; 327 int d = pw2[len]; 328 return min(table[d][x], table[d][y - (1 << d)]); 329 } 330 331 int query(int x, int y) 332 { 333 return query_inner(idx[x], idx[y]); 334 } 335 336 LCP() {}; 337 LCP(vector<string> s) 338 { 339 int n = s.size(); 340 vector<pair<string, int>> t; 341 for(int i = 0; i < n; i++) 342 { 343 t.push_back(make_pair(s[i], i)); 344 } 345 sort(t.begin(), t.end()); 346 idx.resize(n); 347 for(int i = 0; i < n; i++) 348 { 349 idx[t[i].second] = i; 350 } 351 vector<int> LCPs; 352 for(int i = 0; i < n - 1; i++) 353 LCPs.push_back(naiveLCP(t[i].first, t[i + 1].first)); 354 table = build_table(LCPs); 355 }; 356 }; 357 358 const int T = int(2e7); 359 360 map<char, int> nxt[T]; 361 int cur = 1; 362 int root = 0; 363 int cnt[T]; 364 365 void clear_trie() 366 { 367 root = cur++; 368 } 369 370 int go(int x, char c) 371 { 372 if(!nxt[x].count(c)) 373 nxt[x][c] = cur++; 374 return nxt[x][c]; 375 } 376 377 void add(int v, const string& s, int l, int r, int n, bool sw, const vector<int>& ps) 378 { 379 if(sw && l + r < n - 1 && ps[n - r - 1] == ps[l]) 380 { 381 cnt[v]++; 382 } 383 if(sw) 384 { 385 if(l + r < n - 1) 386 add(go(v, s[n - r - 1]), s, l, r + 1, n, sw, ps); 387 } 388 else 389 { 390 add(go(v, '$'), s, l, r, n, true, ps); 391 if(l < n - 1) 392 add(go(v, s[l]), s, l + 1, r, n, sw, ps); 393 } 394 } 395 396 int calc(int v, const string& s, int l, int r, int n, bool sw, const vector<vector<int>>& good) 397 { 398 int ans = 0; 399 if(sw && l + r < n - 1 && good[l][r]) 400 { 401 ans = cnt[v]; 402 } 403 if(sw) 404 { 405 if(l + r < n) 406 ans += calc(go(v, s[n - r - 1]), s, l, r + 1, n, sw, good); 407 } 408 else 409 { 410 ans += calc(go(v, '$'), s, l, r, n, true, good); 411 if(l < n) 412 ans += calc(go(v, s[l]), s, l + 1, r, n, sw, good); 413 } 414 return ans; 415 } 416 417 long long solve_short(vector<string> s, int n) 418 { 419 long long ans = 0; 420 clear_trie(); 421 sort(s.begin(), s.end()); 422 for(int i = 0; i < n; i++) 423 { 424 string cur = s[i]; 425 int len = cur.size(); 426 vector<vector<int>> good(len + 1, vector<int>(len + 1)); 427 for(int l = 0; l < len; l++) 428 { 429 set<char> q; 430 for(int r = l; r < len; r++) 431 { 432 q.insert(cur[r]); 433 if(cur[l] != *q.begin() && cur[r] != *q.rbegin()) 434 { 435 good[l][len - r - 1] = 1; 436 } 437 } 438 } 439 vector<int> p = prefix_sum(sorted_segments(cur)); 440 add(root, cur, 0, 0, len, false, p); 441 ans += calc(root, cur, 0, 0, len, false, good); 442 } 443 ans = n * 1ll * (n - 1) - ans; 444 return ans; 445 } 446 447 long long solve_long(vector<string> s, int n) 448 { 449 int len = s[0].size(); 450 sort(s.begin(), s.end()); 451 vector<string> t = s; 452 for(int i = 0; i < n; i++) 453 reverse(t[i].begin(), t[i].end()); 454 LCP ls(s); 455 LCP lt(t); 456 long long ans = 0; 457 for(int i = 0; i < n; i++) 458 { 459 vector<int> aux = prefix_sum(sorted_segments(s[i])); 460 for(int j = i + 1; j < n; j++) 461 { 462 int lf = ls.query(i, j); 463 int rg = lt.query(i, j); 464 if(aux[len - rg - 1] - aux[lf] == 0) 465 ans++; 466 else 467 ans += 2; 468 } 469 } 470 return ans; 471 } 472 473 long long solve_class(vector<string> s, int n) 474 { 475 if(n <= K) 476 return solve_long(s, n); 477 else 478 return solve_short(s, n); 479 } 480 481 vector<int> get_class(string s) 482 { 483 vector<int> c(26); 484 for(auto x : s) c[x - 'a']++; 485 return c; 486 } 487 488 int main() 489 { 490 pw2[1] = 0; 491 for(int i = 2; i < (1 << LN); i++) 492 pw2[i] = pw2[i >> 1] + 1; 493 int n; 494 cin >> n; 495 vector<string> s(n); 496 for(int i = 0; i < n; i++) 497 cin >> s[i]; 498 long long ans = 0; 499 map<vector<int>, vector<string>> classes; 500 for(int i = 0; i < n; i++) 501 classes[get_class(s[i])].push_back(s[i]); 502 int cnt = 0; 503 for(auto x : classes) 504 { 505 ans += solve_class(x.second, x.second.size()); 506 ans += cnt * 1337ll * x.second.size(); 507 cnt += x.second.size(); 508 } 509 cout << ans << endl; 510 } 511 ```