codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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").