810.md (12107B)
1 Source: https://codeforces.com/blog/entry/52099 2 3 Tutorial is loading... 4 5 **Setter's code** 6 7 ``` 8 int n, k, s = 0; 9 cin >> n >> k; 10 for (int i = 0; i < n; ++i) { 11 int x; 12 cin >> x; 13 s += x; 14 } 15 for (int ans = 0;; ans++) { 16 int a = 2 * (s + ans * k); 17 int b = (2 * k - 1) * (ans + n); 18 19 if (a >= b) { 20 cout << ans; 21 return 0; 22 } 23 } 24 ``` 25 26 First accepted [Zhigan](/profile/Zhigan "Expert Zhigan"). 27 28 Tutorial is loading... 29 30 **Setter's code** 31 32 ``` 33 for (int i = 0; i < n; i++) { 34 cin >> k[i] >> l[i]; 35 a.push_back(make_pair(min(2 * k[i], l[i]) - min(k[i], l[i]), i)); 36 } 37 sort(a.rbegin(), a.rend()); 38 39 long long ans = 0; 40 for (int i = 0; i < f; i++) { 41 int pos = a[i].second; 42 ans += min(2 * k[pos], l[pos]); 43 } 44 for (int i = f; i < n; i++) { 45 int pos = a[i].second; 46 ans += min(k[pos], l[pos]); 47 } 48 cout << ans; 49 ``` 50 51 First accepted [polygonia](/profile/polygonia "Candidate Master polygonia"). 52 53 Tutorial is loading... 54 55 **Setter's code** 56 57 ``` 58 st[0] = 1; 59 for ( int j = 1; j < maxn; j++ ) 60 st[j] = ( 2 * st[j - 1] ) % base; 61 int n; 62 scanf ( "%d", &n ); 63 for ( int j = 0; j < n; j++ ) 64 scanf ( "%d", &a[j] ); 65 sort( a, a + n ); 66 int ans = 0; 67 for ( int j = 1; j < n; j++ ) { 68 int len = a[j] - a[j - 1]; 69 int cntL = j; 70 int cntR = n - j; 71 int add = ( 1LL * ( st[cntL] - 1 + base ) * ( st[cntR] - 1 + base ) ) % base; 72 ans = ( 1LL * ans + 1LL * len * add ) % base; 73 } 74 printf ( "%d\n", ans ); 75 ``` 76 77 First accepted div2: [RaidenEi](/profile/RaidenEi "Specialist RaidenEi"). 78 79 First accepted div1: [Lewin](/profile/Lewin "International Grandmaster Lewin"). 80 81 Tutorial is loading... 82 83 **Setter's code** 84 85 ``` 86 int query(int x,int y){ 87 if(x==-1)return 0; 88 cout<<1<<' '<<x<<' '<<y<<endl; 89 string ret; 90 cin>>ret; 91 return ("TAK"==ret); 92 } 93 94 int get(int l,int r){ 95 if(l>r)return -1; 96 97 while(l<r){ 98 int m=(l+r)/2; 99 if(query(m,m+1)){ 100 r=m; 101 }else l=m+1; 102 } 103 return l; 104 } 105 106 int main() { 107 int n,k; 108 cin>>n>>k; 109 110 int x=get(1,n); 111 int y=get(1,x-1); 112 if(!query(y,x))y=get(x+1,n); 113 cout<<2<<' '<<x<<' '<<y<<endl; 114 115 return 0; 116 } 117 ``` 118 119 First accepted div2: [polygonia](/profile/polygonia "Candidate Master polygonia"). 120 121 First accepted div1: [V--o_o--V](/profile/V--o_o--V "Legendary Grandmaster V--o_o--V"). 122 123 Tutorial is loading... 124 125 **Setter's code** 126 127 ``` 128 ll dp[32][2][2][2]; 129 ll sum[32][2][2][2]; 130 131 void add(ll &x,ll y){ 132 x+=y; 133 if(x>=mod)x-=mod; 134 } 135 136 void sub(ll &x,ll y){ 137 x-=y; 138 if(x<0)x+=mod; 139 } 140 141 ll mul(ll x,ll y){ 142 return x*y%mod; 143 } 144 145 ll pot[32]; 146 147 ll solve(int x,int y,int z){ 148 if(x<0||y<0||z<0)return 0; 149 memset(dp,0,sizeof dp); 150 memset(sum,0,sizeof sum); 151 vi A,B,C; 152 rep(j,0,31){ 153 A.pb(x%2);x/=2; 154 B.pb(y%2);y/=2; 155 C.pb(z%2);z/=2; 156 } 157 reverse(all(A)); 158 reverse(all(B)); 159 reverse(all(C)); 160 dp[0][1][1][1]=1; 161 sum[0][1][1][1]=0; 162 rep(i,0,31){ 163 rep(a,0,2)rep(b,0,2)rep(c,0,2){ 164 rep(x,0,2)rep(y,0,2){ 165 int z=x^y; 166 if(a==1&&A[i]==0&&x==1)continue; 167 if(b==1&&B[i]==0&&y==1)continue; 168 if(c==1&&C[i]==0&&z==1)continue; 169 add(dp[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],dp[i][a][b][c]); 170 add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],sum[i][a][b][c]); 171 add(sum[i+1][a&(A[i]==x)][b&(B[i]==y)][c&(C[i]==z)],mul(z<<(30-i),dp[i][a][b][c])); 172 173 } 174 } 175 } 176 ll res=0; 177 rep(a,0,2)rep(b,0,2)rep(c,0,2){ 178 add(res,sum[31][a][b][c]); 179 add(res,dp[31][a][b][c]); 180 } 181 return res; 182 } 183 184 int main(){ 185 int T; 186 cin>>T; 187 while(T--){ 188 int x,y,x2,y2,k; 189 cin>>x>>y>>x2>>y2>>k; 190 --x;--y;--x2;--y2;--k; 191 ll res=0; 192 add(res,solve(x2,y2,k)); 193 sub(res,solve(x2,y-1,k)); 194 sub(res,solve(x-1,y2,k)); 195 add(res,solve(x-1,y-1,k)); 196 cout<<res<<'\n'; 197 } 198 return 0; 199 } 200 ``` 201 202 First accepted div2: [xsup](/profile/xsup "Expert xsup"). 203 204 First accepted div1: [anta](/profile/anta "International Grandmaster anta"). 205 206 Tutorial is loading... 207 208 **Setter's code** 209 210 ``` 211 struct node { 212 int prior, sz, dp, add; 213 node *l, *r; 214 node ( int x ) { 215 prior = ( rand() << 15 ) | rand(); 216 // sz = 1; 217 dp = x; 218 l = r = NULL; 219 add = 0; 220 } 221 }; 222 223 typedef node * pnode; 224 225 void push( pnode T ) { 226 T -> dp += T -> add; 227 if ( T -> l ) 228 T -> l -> add += T -> add; 229 if ( T -> r ) 230 T -> r -> add += T -> add; 231 T -> add = 0; 232 } 233 234 void merge( pnode &T, pnode L, pnode R ) { 235 if ( !L ) { 236 T = R; 237 return; 238 } 239 if ( !R ) { 240 T = L; 241 return; 242 } 243 if ( L -> prior > R -> prior ) { 244 push( L ); 245 merge( L -> r, L -> r, R ); 246 T = L; 247 return; 248 } 249 push( R ); 250 merge( R -> l, L, R -> l ); 251 T = R; 252 } 253 254 void split( pnode T, int value, pnode &L, pnode &R ) { 255 if ( !T ) { 256 L = R = NULL; 257 return; 258 } 259 push( T ); 260 if ( T -> dp >= value ) { 261 split( T -> l, value, L, T -> l ); 262 R = T; 263 return; 264 } 265 split( T -> r, value, T -> r, R ); 266 L = T; 267 } 268 269 int findBegin( pnode T ) { 270 push( T ); 271 if ( !T -> l ) 272 return T -> dp; 273 return findBegin( T -> l ); 274 } 275 276 int findMax( pnode T, int n ) { 277 if ( !T ) 278 return 0; 279 push( T ); 280 return findMax( T -> l, n ) + findMax( T -> r, n ) + ( T -> dp <= inf ? 1 : 0 ); 281 } 282 283 pair < int, int > a[maxn]; 284 pnode T = new node( 0 ); 285 pnode L = NULL; 286 pnode M = NULL; 287 pnode R = NULL; 288 pnode rubbish = NULL; 289 290 void solve() { 291 int n; 292 scanf ( "%d", &n ); 293 for ( int j = 1; j <= n; j++ ) 294 scanf ( "%d%d", &a[j].f, &a[j].s ); 295 for ( int j = 1; j <= n; j++ ) 296 merge( T, T, new node( inf + j ) ); 297 for ( int j = 1; j <= n; j++ ) { 298 split( T, a[j].f, L, R ); 299 split( R, a[j].s, M, R ); 300 if ( M ) 301 M -> add += 1; 302 int cnt = findBegin( R ); 303 split( R, cnt + 1, rubbish, R ); 304 merge( T, L, new node( a[j].f ) ); 305 merge( T, T, M ); 306 merge( T, T, R ); 307 } 308 printf ( "%d\n", findMax( T, n ) - 1 ); 309 } 310 ``` 311 312 First accepted: [ksun48](/profile/ksun48 "International Grandmaster ksun48"). 313 314 Tutorial is loading... 315 316 **Setter's code** 317 318 ``` 319 #include <functional> 320 #include <algorithm> 321 #include <iostream> 322 #include <fstream> 323 #include <cstdlib> 324 #include <numeric> 325 #include <iomanip> 326 #include <cstdio> 327 #include <cstring> 328 #include <cassert> 329 #include <vector> 330 #include <math.h> 331 #include <queue> 332 #include <stack> 333 #include <ctime> 334 #include <set> 335 #include <map> 336 337 using namespace std; 338 339 typedef long long ll; 340 typedef long double ld; 341 342 template <typename T> 343 T nextInt() { 344 T x = 0, p = 1; 345 char ch; 346 do { ch = getchar(); } while(ch <= ' '); 347 if (ch == '-') { 348 p = -1; 349 ch = getchar(); 350 } 351 while(ch >= '0' && ch <= '9') { 352 x = x * 10 + (ch - '0'); 353 ch = getchar(); 354 } 355 return x * p; 356 } 357 const int maxN = (int)2e5 + 10; 358 const int maxL = 17; 359 const int INF = (int)1e9; 360 const int mod = (int)1e9 + 7; 361 const ll LLINF = (ll)1e18 + 5; 362 363 int mul(int x, int y) { 364 return 1LL * x * y % mod; 365 } 366 367 void add(int &x, int y) { 368 x += y; 369 if (x >= mod) x -= mod; 370 } 371 372 void sub(int &x, int y) { 373 x -= y; 374 if (x < 0) x += mod; 375 } 376 377 int n; 378 vector <int> g[maxN]; 379 vector <int> d[maxN]; 380 vector <int> coefs[maxN]; 381 int phi[maxN]; 382 int inv[maxN]; 383 int a[maxN]; 384 385 int tmp[maxN]; 386 387 void productToTmp(int a, int b) { 388 for (size_t it = 0; it < d[a].size(); it++) { 389 for (size_t jt = 0; jt < d[b].size(); jt++) { 390 int x = d[a][it]; 391 int cx = coefs[a][it]; 392 int y = d[b][jt]; 393 int cy = coefs[b][jt]; 394 add(tmp[x * y], mul(cx, cy)); 395 } 396 } 397 } 398 399 void precalc() { 400 inv[1] = 1; 401 for (int i = 1; i < maxN; ++i) { 402 phi[i] = i; 403 if(i > 1) inv[i] = mul(mod - mod / i, inv[mod % i]); 404 } 405 for (int i = 1; i < maxN; ++i) { 406 for (int j = i; j < maxN; j += i) { 407 d[j].push_back(i); 408 if (j != i) phi[j] -= phi[i]; 409 } 410 } 411 for (int i = 1; i < maxN; ++i) { 412 coefs[i].resize(d[i].size()); 413 } 414 coefs[1][0] = 1; 415 for (int x = 2; x < maxN; x++) { 416 if ((int)d[x].size() == 2) { 417 coefs[x][0] = 1; 418 coefs[x][1] = inv[x - 1]; 419 } else { 420 int lp = d[x][1]; 421 int z = x; 422 while (z % lp == 0) { 423 z /= lp; 424 } 425 for (int y: d[x]) { 426 tmp[y] = 0; 427 } 428 productToTmp(lp, z); 429 for (size_t it = 0; it < d[x].size(); it++) { 430 coefs[x][it] = tmp[d[x][it]]; 431 } 432 } 433 } 434 } 435 436 int nodes[maxN]; 437 int len = 0; 438 int sz[maxN]; 439 int blocked[maxN]; 440 int level[maxN]; 441 int anc[maxN]; 442 443 void calc_sizes(int v, int p = -1) { 444 nodes[len++] = v; 445 sz[v] = 1; 446 anc[v] = p; 447 for (int x: g[v]){ 448 if (blocked[x] || x == p) continue; 449 calc_sizes(x, v); 450 sz[v] += sz[x]; 451 } 452 } 453 454 int sum_phi[maxN]; 455 456 int list_len; 457 int list[maxN]; 458 int depth[maxN]; 459 460 void get_list(int v, int par = -1, int dpth = 1) { 461 list[list_len] = v; 462 depth[list_len++] = dpth; 463 for (int x: g[v]) { 464 if (par == x || blocked[x]) continue; 465 get_list(x, v, dpth + 1); 466 } 467 } 468 469 int sum[maxN]; 470 471 int calc(int value) { 472 int cur = 0; 473 for(size_t i = 0; i < d[value].size(); ++i) { 474 int x = d[value][i]; 475 add(cur, mul(sum_phi[x], coefs[value][i])); 476 } 477 return mul(cur, phi[value]); 478 } 479 480 int total = 0; 481 482 void solve(int root) { //root is a centroid 483 for (int i = 0; i < len; ++i) { 484 int u = nodes[i]; 485 int y = a[u]; 486 for (int x: d[y]) { 487 add(sum_phi[x], phi[y]); 488 } 489 } 490 for (int child: g[root]) { 491 if (blocked[child]) continue; 492 493 list_len = 0; 494 get_list(child, root); 495 { 496 //excluding everything which can be counted twice 497 for(int i = 0; i < list_len; ++i) { 498 int u = list[i]; 499 int y = a[u]; 500 for(int x: d[y]) { 501 sub(sum_phi[x], phi[y]); 502 } 503 } 504 } 505 { 506 for (int i = 0; i < list_len; ++i) { 507 int u = list[i]; 508 int d = depth[i]; 509 int value = a[u]; 510 add(total, mul(d, calc(value))); 511 } 512 } 513 { 514 //including back 515 for(int i = 0; i < list_len; ++i) { 516 int u = list[i]; 517 int y = a[u]; 518 for(int x: d[y]) { 519 add(sum_phi[x], phi[y]); 520 } 521 } 522 } 523 } 524 525 //clear 526 for (int i = 0; i < len; ++i) { 527 int u = nodes[i]; 528 int y = a[u]; 529 for (int x: d[y]) { 530 sum_phi[x] = 0; 531 } 532 } 533 } 534 535 void build(int v, int lev) { 536 len = 0; 537 calc_sizes(v); 538 int centroid = -1; 539 for (int i = 0; i < len; ++i) { 540 int u = nodes[i]; 541 int maxChildSize = len - sz[u]; 542 for (int x: g[u]) { 543 if (x != anc[u] && !blocked[x]) { 544 maxChildSize = max(maxChildSize, sz[x]); 545 } 546 } 547 if (maxChildSize <= len / 2) { 548 centroid = u; 549 } 550 } 551 blocked[centroid] = true; 552 level[centroid] = lev; 553 solve(centroid); 554 555 for (int x: g[centroid]) { 556 if (blocked[x]) continue; 557 build(x, lev + 1); 558 } 559 } 560 561 int main() { 562 563 // freopen("input.txt", "r", stdin); 564 // freopen("output.txt", "w", stdout); 565 ios_base::sync_with_stdio(0); 566 precalc(); 567 cin >> n; 568 for (int i = 0; i < n; ++i) { 569 cin >> a[i]; 570 } 571 for (int i = 1; i < n; ++i) { 572 int x, y; 573 cin >> x >> y; 574 --x; --y; 575 g[x].push_back(y); 576 g[y].push_back(x); 577 } 578 579 build(0, 0); 580 581 total = mul(total, inv[n]); 582 total = mul(total, inv[n - 1]); 583 total = mul(total, 2); 584 585 cout << total << endl; 586 return 0; 587 } 588 ``` 589 590 First accepted: [radoslav11](/profile/radoslav11 "Candidate Master radoslav11").