819.md (8926B)
1 Source: https://codeforces.com/blog/entry/52946 2 3 First, I apologize for problems with round and serious problem with Div1A/Div2C. It was very important round for me and, as always, something goes wrong. [KAN](/profile/KAN "Grandmaster KAN") have already [wrote about this](//codeforces.com/blog/entry/52944). 4 5 Anyway, there are problems, so editorial must exists. Due some circumstances, Editorial will be upload in parts. Also, most of tutorials will contain main ideas how to solve task, not ready algorithm. 6 7 Tutorial is loading... 8 9 **code** 10 11 ``` 12 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 13 #define forn(i, n) fore(i, 0, n) 14 15 int c, l, v0, v1, a; 16 17 inline bool read() { 18 if(!(cin >> c >> v0 >> v1 >> a >> l)) 19 return false; 20 21 return true; 22 } 23 24 inline void solve() { 25 int pos = v0; 26 int t = 1; 27 28 int add = v0; 29 30 while(pos < c) { 31 add = min(v1, add + a); 32 33 pos += add - l; 34 t++; 35 } 36 37 cout << t << endl; 38 } 39 ``` 40 41 Tutorial is loading... 42 43 **code** 44 45 ``` 46 int n, a; 47 48 inline bool read() { 49 if(!(cin >> n >> a)) 50 return false; 51 52 return true; 53 } 54 55 inline void solve() { 56 int base = n * a / 180; 57 base = max(1, min(n - 2, base)); 58 59 int bk = base; 60 for(int ck = max(1, base - 2); ck <= min(n - 2, base + 2); ck++) { 61 if(abs(180 * ck - n * a) < abs(180 * bk - n * a)) 62 bk = ck; 63 } 64 65 cout << 2 << " " << 1 << " " << bk + 2 << endl; 66 } 67 ``` 68 69 Tutorial is loading... 70 71 **code** 72 73 Tutorial is loading... 74 75 **code** 76 77 ``` 78 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 79 #define forn(i, n) fore(i, 0, n) 80 81 typedef long long li; 82 83 const int N = 1000 * 1000 + 555; 84 85 int n, p[N]; 86 87 inline bool read() { 88 if(!(cin >> n)) 89 return false; 90 forn(i, n) 91 assert(scanf("%d", &p[i]) == 1); 92 return true; 93 } 94 95 li sum[N], df[N], res[N]; 96 97 inline void add(int lf, int rg, int k, int b) { 98 if(lf > rg) 99 return; 100 101 sum[lf] += b; 102 df[lf] += k; 103 104 sum[rg + 1] -= b + k * 1ll * (rg - lf); 105 df[rg] -= k; 106 } 107 108 inline void calc() { 109 li curdf = 0; 110 forn(i, n) { 111 sum[i] += curdf; 112 curdf += df[i]; 113 } 114 115 li cursm = 0; 116 forn(i, n) { 117 cursm += sum[i]; 118 res[i] += cursm; 119 } 120 } 121 122 inline void solve() { 123 memset(sum, 0, sizeof sum); 124 memset(df, 0, sizeof df); 125 memset(res, 0, sizeof res); 126 127 forn(i, n) { 128 int c1 = i + 1, p1 = 0; 129 int c2 = n, p2 = p1 + c2 - c1; 130 int c3 = i, p3 = p2 + c3; 131 132 if(p[i] <= c3) { 133 add(p1, p2, 1, c1 - p[i]); 134 add(p2 + 1, p2 + p[i], -1, p[i] - 1); 135 add(p2 + p[i] + 1, p3, 1, 1); 136 } else { 137 add(p1, p1 + p[i] - c1, -1, p[i] - c1); 138 add(p1 + p[i] - c1 + 1, p2, 1, 1); 139 add(p2 + 1, p3, -1, p[i] - 1); 140 } 141 } 142 143 calc(); 144 145 int ans = 0; 146 forn(i, n) 147 if(res[ans] > res[i]) 148 ans = i; 149 150 cout << res[ans] << " " << ans << endl; 151 } 152 ``` 153 154 Tutorial is loading... 155 156 **code** 157 158 ``` 159 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 160 #define forn(i, n) fore(i, 0, n) 161 162 #define all(a) (a).begin(), (a).end() 163 #define sqr(a) ((a) * (a)) 164 #define sz(a) int(a.size()) 165 #define mp make_pair 166 #define pb push_back 167 168 typedef long long li; 169 typedef pair<int, int> pt; 170 typedef pair<li, li> ptl; 171 172 const int INF = int(1e9); 173 const li INF64 = li(INF) * INF; 174 175 int n[3], m[3], s[3]; 176 177 inline bool read() { 178 if(scanf("%d %d %d", &n[0], &n[1], &n[2]) != 3) 179 return false; 180 forn(i, 3) 181 assert(scanf("%d", &m[i]) == 1); 182 forn(i, 3) 183 assert(scanf("%d", &s[i]) == 1); 184 return true; 185 } 186 187 const int N = 2 * 1000 * 1000 + 55; 188 int ls[N]; 189 190 inline void precalc() { 191 memset(ls, -1, sizeof ls); 192 193 ls[0] = ls[1] = 1; 194 fore(i, 2, N) { 195 if(ls[i] != -1) 196 continue; 197 198 ls[i] = i; 199 for(li j = i * 1ll * i; j < N; j += i) 200 if(ls[j] == -1) 201 ls[j] = i; 202 } 203 } 204 205 inline vector<pt> fact(int n[3]) { 206 vector<int> divs; 207 208 forn(i, 3) { 209 int cur = n[i]; 210 while(ls[cur] != cur) { 211 divs.pb(ls[cur]); 212 cur /= ls[cur]; 213 } 214 if(cur > 1) 215 divs.pb(cur); 216 } 217 218 sort(all(divs)); 219 vector<pt> ans; 220 221 int u = 0; 222 while(u < sz(divs)) { 223 int v = u; 224 while(v < sz(divs) && divs[v] == divs[u]) 225 v++; 226 227 ans.pb(mp(divs[u], v - u)); 228 u = v; 229 } 230 231 return ans; 232 } 233 234 li ans; 235 236 li nn, mm, ss; 237 vector<pt> fs; 238 vector<li> bad; 239 240 void calcDivs(int pos, li val) { 241 if(pos >= sz(fs)) { 242 ans += (val <= nn); 243 return; 244 } 245 246 li cv = 1; 247 forn(i, fs[pos].y + 1) { 248 calcDivs(pos + 1, val * cv); 249 250 cv *= fs[pos].x; 251 } 252 } 253 254 void calcInEx(int pos, li val, int cnt) { 255 if(pos >= sz(bad)) { 256 li k = cnt ? -1 : 1; 257 258 ans += k * (mm / val); 259 return; 260 } 261 262 calcInEx(pos + 1, val, cnt); 263 calcInEx(pos + 1, val * bad[pos], cnt ^ 1); 264 } 265 266 inline void solve() { 267 ans = 0; 268 s[0] *= 2; 269 270 nn = n[0] * 1ll * n[1] * 1ll * n[2]; 271 mm = m[0] * 1ll * m[1] * 1ll * m[2]; 272 ss = s[0] * 1ll * s[1] * 1ll * s[2]; 273 274 fs = fact(s); 275 calcDivs(0, 1); 276 277 bad.clear(); 278 vector<pt> fn = fact(n); 279 280 forn(i, sz(fn)) { 281 li cv = fn[i].x; 282 forn(k, fn[i].y) { 283 if(ss % cv != 0) { 284 bad.pb(cv); 285 break; 286 } 287 cv *= fn[i].x; 288 } 289 } 290 291 calcInEx(0, 1, 0); 292 293 printf("%I64d\n", ans); 294 } 295 ``` 296 297 Tutorial is loading... 298 299 **code** 300 301 ``` 302 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 303 #define forn(i, n) fore(i, 0, n) 304 305 #define all(a) (a).begin(), (a).end() 306 #define sqr(a) ((a) * (a)) 307 #define sz(a) int(a.size()) 308 #define mp make_pair 309 #define pb push_back 310 311 #define x first 312 #define y second 313 314 typedef long long li; 315 typedef long double ld; 316 typedef pair<int, int> pt; 317 318 const int INF = int(1e9); 319 const li INF64 = li(INF) * INF; 320 321 int gcd(int a, int b) { 322 if(a == 0) 323 return b; 324 return gcd(b % a, a); 325 } 326 327 int exgcd(int a, li &x, int b, li &y) { 328 if(a == 0) { 329 x = 0, y = 1; 330 return b; 331 } 332 333 li xx, yy; 334 int g = exgcd(b % a, xx, a, yy); 335 336 x = yy - b / a * xx; 337 y = xx; 338 339 return g; 340 } 341 342 const int N = 200 * 1000 + 555; 343 int t, n, a[N]; 344 345 inline bool read() { 346 if(!(cin >> t >> n)) 347 return false; 348 forn(i, n) 349 assert(scanf("%d", &a[i]) == 1); 350 return true; 351 } 352 353 int pf[N], s; 354 355 inline li up(li a, li b) { 356 return (a + b - 1) / b; 357 } 358 359 inline int findPos(int a, int b, int c) { 360 li x, y; 361 int g = exgcd(a, x, b, y); 362 assert(c % g == 0); 363 364 x *= +c / g; 365 y *= -c / g; 366 assert(a * 1ll * x - b * 1ll * y == c); 367 368 int ag = a / g; 369 int bg = b / g; 370 371 li k = 0; 372 if(x < 0) 373 k = up(-x, bg); 374 if(x >= bg) 375 k = -up(x - bg, bg); 376 x += bg * k; 377 y += ag * k; 378 379 assert(0 <= x && x < bg); 380 381 k = 0; 382 if(y < 0) 383 k = up(-y, ag); 384 x += bg * k; 385 y += ag * k; 386 387 return x; 388 } 389 390 map< int, set<pt> > cycle; 391 392 int ans[N]; 393 394 inline void solve() { 395 cycle.clear(); 396 pf[0] = 0; 397 fore(i, 1, n) 398 pf[i] = (pf[i - 1] + a[i]) % t; 399 400 s = (a[0] + pf[n - 1]) % t; 401 int g = gcd(s, t); 402 403 forn(i, n) { 404 int st = pf[i] % g; 405 auto& cc = cycle[st]; 406 407 int pos = findPos(s, t, pf[i] - st); 408 409 if(cc.empty()) { 410 ans[i] += t / g; 411 cc.insert(pt(pos, -i)); 412 } else { 413 auto rg = cc.lower_bound(pt(pos, -i)); 414 if(rg == cc.end()) { 415 ans[i] += t / g - pos; 416 rg = cc.begin(); 417 ans[i] += rg->x; 418 } else 419 ans[i] += rg->x - pos; 420 421 auto lf = cc.lower_bound(pt(pos, -i)); 422 if(lf == cc.begin()) 423 lf = --cc.end(); 424 else 425 lf--; 426 ans[ -(lf->y) ] -= ans[i]; 427 428 cc.insert(pt(pos, -i)); 429 } 430 } 431 432 forn(i, n) 433 printf("%d ", ans[i]); 434 puts(""); 435 } 436 ``` 437 438 Tutorial is loading... 439 440 **code** 441 442 ``` 443 #include <bits/stdc++.h> 444 445 using namespace std; 446 447 using ll = long long; 448 using ld = long double; 449 using D = double; 450 using uint = unsigned int; 451 template<typename T> 452 using pair2 = pair<T, T>; 453 454 #ifdef WIN32 455 #define LLD "%I64d" 456 #else 457 #define LLD "%lld" 458 #endif 459 460 #define pb push_back 461 #define mp make_pair 462 #define all(x) (x).begin(),(x).end() 463 #define fi first 464 #define se second 465 466 const int maxn = 305; 467 468 int pair3[maxn]; 469 int n; 470 vector<vector<int>> answer; 471 472 void add3(int a, int b, int c) 473 { 474 answer.pb({a, b, c}); 475 } 476 477 void add4(int a, int b, int c, int d) 478 { 479 answer.pb({a, b, c, d}); 480 } 481 482 int main() 483 { 484 cin >> n; 485 if (n % 2 == 0) 486 { 487 pair3[0] = 3; // 0 1 3 488 pair3[2] = 1; // 2 3 1 489 add3(0, 1, 2); 490 add3(2, 3, 0); 491 for (int i = 4; i < n; i += 2) 492 { 493 add4(0, pair3[0], 1, i); 494 add3(i, i + 1, 0); 495 pair3[i] = 1; 496 pair3[0] = i + 1; 497 for (int j = 2; j < i; j += 2) 498 { 499 add4(j, pair3[j], j + 1, i); 500 add4(j, i, j + 1, i + 1); 501 pair3[j] = i + 1; 502 } 503 } 504 for (int i = 0; i < n; i += 2) 505 { 506 add3(i, i + 1, pair3[i]); 507 } 508 } else 509 { 510 pair3[1] = 0; // 1 2 0 511 add3(0, 1, 2); 512 for (int i = 3; i < n; i += 2) 513 { 514 add3(i, i + 1, 0); 515 pair3[i] = 0; 516 for (int j = 1; j < i; j += 2) 517 { 518 add4(j, pair3[j], j + 1, i); 519 add4(j, i, j + 1, i + 1); 520 pair3[j] = i + 1; 521 } 522 } 523 for (int i = 1; i < n; i += 2) 524 { 525 add3(i, i + 1, pair3[i]); 526 } 527 } 528 printf("%d\n", (int)answer.size()); 529 for (auto &t : answer) 530 { 531 printf("%d", (int)t.size()); 532 for (auto t2 : t) printf(" %d", t2 + 1); 533 printf("\n"); 534 } 535 return 0; 536 } 537 ```