1701.md (9372B)
1 Source: https://codeforces.com/blog/entry/104671 2 3 [1701A - Grass Field](/contest/1701/problem/A "Educational Codeforces Round 131 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (vovuh)** 12 13 ``` 14 for _ in range(int(input())): 15 a = [list(map(int, input().split())) for i in range(2)] 16 cnt = sum([sum(a[i]) for i in range(2)]) 17 if cnt == 0: 18 print(0) 19 elif cnt == 4: 20 print(2) 21 else: 22 print(1) 23 ``` 24 25 [1701B - Permutation](/contest/1701/problem/B "Educational Codeforces Round 131 (Rated for Div. 2)") 26 27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution (Neon)** 34 35 ``` 36 #include <bits/stdc++.h> 37 38 using namespace std; 39 40 int main() { 41 ios::sync_with_stdio(false); cin.tie(0); 42 int t; 43 cin >> t; 44 while (t--) { 45 int n; 46 cin >> n; 47 cout << 2 << '\n'; 48 for (int i = 1; i <= n; ++i) if (i % 2 != 0) 49 for (int j = i; j <= n; j *= 2) 50 cout << j << ' '; 51 cout << '\n'; 52 } 53 } 54 ``` 55 56 [1701C - Schedule Management](/contest/1701/problem/C "Educational Codeforces Round 131 (Rated for Div. 2)") 57 58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 59 60 **Tutorial** 61 62 Tutorial is loading... 63 64 **Solution (awoo)** 65 66 ``` 67 #include <bits/stdc++.h> 68 69 #define forn(i, n) for (int i = 0; i < int(n); i++) 70 71 using namespace std; 72 73 int main() { 74 int t; 75 scanf("%d", &t); 76 while (t--){ 77 int n, m; 78 scanf("%d%d", &n, &m); 79 vector<int> a(m); 80 forn(i, m){ 81 scanf("%d", &a[i]); 82 --a[i]; 83 } 84 vector<int> cnt(n); 85 forn(i, m) ++cnt[a[i]]; 86 auto check = [&](int t){ 87 long long fr = 0, need = 0; 88 forn(i, n){ 89 if (t >= cnt[i]) 90 fr += (t - cnt[i]) / 2; 91 else 92 need += cnt[i] - t; 93 } 94 return need <= fr; 95 }; 96 int l = 0, r = 2 * m; 97 int res = -1; 98 while (l <= r){ 99 int m = (l + r) / 2; 100 if (check(m)){ 101 res = m; 102 r = m - 1; 103 } 104 else{ 105 l = m + 1; 106 } 107 } 108 printf("%d\n", res); 109 } 110 return 0; 111 } 112 ``` 113 114 [1701D - Permutation Restoration](/contest/1701/problem/D "Educational Codeforces Round 131 (Rated for Div. 2)") 115 116 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution (Neon)** 123 124 ``` 125 #include <bits/stdc++.h> 126 127 using namespace std; 128 129 int main() { 130 ios::sync_with_stdio(false); cin.tie(0); 131 int t; 132 cin >> t; 133 while (t--) { 134 int n; 135 cin >> n; 136 vector<int> a(n), b(n); 137 for (int& x : b) cin >> x; 138 vector<pair<int, int>> ev(n); 139 for (int i = 0; i < n; ++i) 140 ev[i] = {(i + 1) / (b[i] + 1) + 1, i}; 141 sort(ev.begin(), ev.end()); 142 set<pair<int, int>> s; 143 int j = 0; 144 for (int i = 1; i <= n; ++i) { 145 while (j < n && ev[j].first == i) { 146 int id = ev[j++].second; 147 s.insert({b[id] ? (id + 1) / b[id] : n, id}); 148 } 149 a[s.begin()->second] = i; 150 s.erase(s.begin()); 151 } 152 for (int& x : a) cout << x << ' '; 153 cout << '\n'; 154 } 155 } 156 ``` 157 158 [1701E - Text Editor](/contest/1701/problem/E "Educational Codeforces Round 131 (Rated for Div. 2)") 159 160 Idea: [vovuh](/profile/vovuh "Master vovuh") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution (vovuh)** 167 168 ``` 169 #include <bits/stdc++.h> 170 171 using namespace std; 172 173 vector<int> zf(const string &s) { 174 int n = s.size(); 175 vector<int> z(n); 176 int l = 0, r = 0; 177 for (int i = 1; i < n; ++i) { 178 if (i <= r) { 179 z[i] = min(r - i + 1, z[i - l]); 180 } 181 while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { 182 ++z[i]; 183 } 184 if (i + z[i] - 1 > r) { 185 l = i; 186 r = i + z[i] - 1; 187 } 188 } 189 return z; 190 } 191 192 int main() { 193 #ifdef _DEBUG 194 freopen("input.txt", "r", stdin); 195 // freopen("output.txt", "w", stdout); 196 #endif 197 198 int T; 199 cin >> T; 200 while (T--) { 201 int n, m; 202 string s, t; 203 cin >> n >> m >> s >> t; 204 205 int ans = 1e9; 206 207 bool bad = false; 208 vector<int> lpos(m), rpos(m); 209 for (int i = 0; i < m; ++i) { 210 if (i > 0) { 211 lpos[i] = lpos[i - 1] + 1; 212 } else { 213 lpos[i] = 0; 214 } 215 while (lpos[i] < n && s[lpos[i]] != t[i]) { 216 ++lpos[i]; 217 } 218 if (lpos[i] >= n) { 219 bad = true; 220 break; 221 } 222 } 223 for (int i = m - 1; i >= 0; --i) { 224 if (i + 1 < m) { 225 rpos[i] = rpos[i + 1] - 1; 226 } else { 227 rpos[i] = n - 1; 228 } 229 while (rpos[i] >= 0 && s[rpos[i]] != t[i]) { 230 --rpos[i]; 231 } 232 if (rpos[i] < 0) { 233 bad = true; 234 break; 235 } 236 } 237 if (bad) { 238 cout << -1 << endl; 239 continue; 240 } 241 242 for (int pos = 0; pos <= n; ++pos) { 243 string tmp = s.substr(0, pos); 244 reverse(tmp.begin(), tmp.end()); 245 tmp += "#" + t; 246 reverse(tmp.begin() + pos + 1, tmp.end()); 247 vector<int> z = zf(tmp); 248 for (int suf = 0; suf <= m; ++suf) { 249 if (pos - suf < 0) { 250 continue; 251 } 252 if (suf < m && rpos[suf] < pos) { 253 continue; 254 } 255 if (suf - 1 >= 0 && lpos[suf - 1] > pos) { 256 continue; 257 } 258 int rg = 0; 259 if (suf != 0) { 260 int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf); 261 rg = (sum != 0) + sum; 262 } else { 263 rg = pos; 264 } 265 ans = min(ans, (n - pos) + rg); 266 } 267 } 268 cout << ans << endl; 269 } 270 271 return 0; 272 } 273 ``` 274 275 [1701F - Points](/contest/1701/problem/F "Educational Codeforces Round 131 (Rated for Div. 2)") 276 277 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 278 279 **Tutorial** 280 281 Tutorial is loading... 282 283 **Solution (BledDest)** 284 285 ``` 286 #include<bits/stdc++.h> 287 288 using namespace std; 289 290 const int N = 200043; 291 const int M = 200001; 292 293 typedef array<long long, 3> vec; 294 typedef array<vec, 3> mat; 295 296 vec operator+(const vec& a, const vec& b) 297 { 298 vec c; 299 for(int i = 0; i < 3; i++) c[i] = a[i] + b[i]; 300 return c; 301 } 302 303 vec operator-(const vec& a, const vec& b) 304 { 305 vec c; 306 for(int i = 0; i < 3; i++) c[i] = a[i] - b[i]; 307 return c; 308 } 309 310 vec operator*(const mat& a, const vec& b) 311 { 312 vec c; 313 for(int i = 0; i < 3; i++) c[i] = 0; 314 for(int i = 0; i < 3; i++) 315 for(int j = 0; j < 3; j++) 316 c[i] += a[i][j] * b[j]; 317 return c; 318 } 319 320 mat operator*(const mat& a, const mat& b) 321 { 322 mat c; 323 for(int i = 0; i < 3; i++) 324 for(int j = 0; j < 3; j++) 325 c[i][j] = 0; 326 for(int i = 0; i < 3; i++) 327 for(int j = 0; j < 3; j++) 328 for(int k = 0; k < 3; k++) 329 c[i][k] += a[i][j] * b[j][k]; 330 return c; 331 } 332 333 mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})}; 334 mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})}; 335 mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})}; 336 337 vec S = {1, 0, 0}; 338 vec Z = {0, 0, 0}; 339 340 vec t[4 * N]; 341 mat f[4 * N]; 342 bool active[4 * N]; 343 bool has[N]; 344 int d, q; 345 346 vec getVal(int v) 347 { 348 if(!active[v]) return Z; 349 return f[v] * t[v]; 350 } 351 352 void recalc(int v) 353 { 354 t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2); 355 } 356 357 void build(int v, int l, int r) 358 { 359 if(l == r - 1) 360 { 361 f[v] = E; 362 t[v] = S; 363 active[v] = false; 364 } 365 else 366 { 367 int m = (l + r) / 2; 368 build(v * 2 + 1, l, m); 369 build(v * 2 + 2, m, r); 370 f[v] = E; 371 recalc(v); 372 active[v] = true; 373 } 374 } 375 376 void push(int v) 377 { 378 if(f[v] == E) return; 379 t[v] = f[v] * t[v]; 380 f[v * 2 + 1] = f[v] * f[v * 2 + 1]; 381 f[v * 2 + 2] = f[v] * f[v * 2 + 2]; 382 f[v] = E; 383 } 384 385 void updSegment(int v, int l, int r, int L, int R, bool adv) 386 { 387 if(L >= R) return; 388 if(l == L && r == R) 389 { 390 if(adv) f[v] = F * f[v]; 391 else f[v] = B * f[v]; 392 return; 393 } 394 push(v); 395 int m = (l + r) / 2; 396 updSegment(v * 2 + 1, l, m, L, min(m, R), adv); 397 updSegment(v * 2 + 2, m, r, max(m, L), R, adv); 398 recalc(v); 399 } 400 401 void setState(int v, int l, int r, int pos, bool val) 402 { 403 if(l == r - 1) 404 { 405 active[v] = val; 406 return; 407 } 408 push(v); 409 int m = (l + r) / 2; 410 if(pos < m) 411 setState(v * 2 + 1, l, m, pos, val); 412 else 413 setState(v * 2 + 2, m, r, pos, val); 414 recalc(v); 415 } 416 417 void addPoint(int x) 418 { 419 int lf = max(0, x - d); 420 int rg = x; 421 if(lf < rg) 422 updSegment(0, 0, M, lf, rg, true); 423 setState(0, 0, M, x, true); 424 } 425 426 void delPoint(int x) 427 { 428 int lf = max(0, x - d); 429 int rg = x; 430 if(lf < rg) 431 updSegment(0, 0, M, lf, rg, false); 432 setState(0, 0, M, x, false); 433 } 434 435 void query(int x) 436 { 437 if(has[x]) 438 { 439 has[x] = false; 440 delPoint(x); 441 } 442 else 443 { 444 has[x] = true; 445 addPoint(x); 446 } 447 vec res = getVal(0); 448 printf("%lld\n", (res[2] - res[1]) / 2); 449 } 450 451 int main() 452 { 453 scanf("%d %d", &q, &d); 454 build(0, 0, M); 455 for(int i = 0; i < q; i++) 456 { 457 int x; 458 scanf("%d", &x); 459 query(x); 460 } 461 } 462 ```