oj.uz

Submission #28686

# Submission time Handle Problem Language Result Execution time Memory
28686 2017-07-16T08:42:44 Z samir_droubi ČVENK (COI15_cvenk) C++14
100 / 100
 779 ms 2804 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int mxn=(1e5)+5;
int ax[mxn];
int ay[mxn];

void fix(int &x, int &y, int &k, int t) {
  if (x) t = min(t, x & -x);
  if (y) t = min(t, y & -y);
  if (!y || (x && (x & -x) < (y & -y)))
    x -= t;
  else
    y -= t;
  k -= t;
}

void kth(int &x, int &y, int k) {
  while (k) fix(x, y, k, k);
}

void lca(int &x , int &y , int xx , int yy)
{
    if(x+y>xx+yy)
    {
        swap( x , xx );
        swap( y , yy );
    }
    int dif= xx + yy - x - y;
    for(int i=30 ; i >= 0 ; --i )
    {
        if( (1<<i) & dif )
            kth( xx , yy , (1<<i) );
    }
    if( x == xx && y == yy)return;
    for(int i = 30 ; i >= 0 ; --i )
    {
        if( (1<<i) > x + y || (1<<i) > xx + yy )continue;
        int x1 = x , y1 = y;
        int xx2 = xx, yy2 = yy;
        kth( x1 , y1 , (1<<i) );
        kth( xx2 , yy2 , (1<<i) );
        if( x1 == xx2 && y1 == yy2)continue;
        x=x1;
        y=y1;
        xx=xx2;
        yy=yy2;
    }
    kth(x,y,1);
}
ll dist(int x, int y, int xx, int yy)
{
    int xxx=x;
    int yyy=y;
    lca(xxx,yyy,xx,yy);
    return 1LL*x + y + xx + yy - 2LL * ( xxx + yyy );
}

bool check(int x, int y, int xx, int yy)
{
    if( x + y > xx + yy )return false;
    kth(xx, yy, xx + yy - x - y );
    return x == xx && y == yy;
}
int sum(int x, int y)
{
    int ans=0;
    for(int i = 1; i <= n ; ++i )
        ans+=check(x, y, ax[i], ay[i]);
    return ans;
}

ll calc(int x,int y)
{
    if( 2 * sum(x, y) < n)
    {
        int mxlog=0;
        while( (1LL << mxlog) <= x + y)++mxlog;
        for(int i = mxlog - 1 ; i >= 0; --i)
        {
            if( (1<<i) > x + y )continue;
            int xx=x;
            int yy=y;
            kth(xx, yy, (1<<i) );
            if( 2 * sum(xx, yy) < n)
            {
                x=xx;
                y=yy;
            }
        }
        kth(x, y, 1);
    }
    if( ( ( x + 1 ) & y)==0 && 2 * sum(x + 1, y) >= n)return -1;
    if( ( ( y + 1 ) & x)==0 && 2 * sum(x, y + 1) >= n)return -1;

    ll ans=0;
    for(int i = 1 ; i <= n ; ++i )
        ans+=dist(x, y, ax[i], ay[i]);
    return ans;
}
int main()
{
    scanf("%d", &n);
    for(int i=1 ; i <= n; ++i )
        scanf("%d%d", &ax[i] , &ay[i] );

    if(n == 2)
    {
        printf("%lld\n", dist(ax[1], ay[1], ax[2], ay[2]));
        return 0;
    }

    while(true)
    {
        int r= ( rand()%n ) +1;
        ll ans=calc(ax[r], ay[r]);
        if(ans==-1)continue;
        printf("%lld\n",ans);
        break;
    }
    return 0;
}

Compilation message

cvenk.cpp: In function 'int main()':
cvenk.cpp:104:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
cvenk.cpp:106:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &ax[i] , &ay[i] );
                                        ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 0 ms 2804 KB Output is correct
3 Correct 0 ms 2804 KB Output is correct
4 Correct 0 ms 2804 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2804 KB Output is correct
2 Correct 203 ms 2804 KB Output is correct
3 Correct 49 ms 2804 KB Output is correct
4 Correct 46 ms 2804 KB Output is correct
5 Correct 59 ms 2804 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 2804 KB Output is correct
2 Correct 773 ms 2804 KB Output is correct
3 Correct 279 ms 2804 KB Output is correct
4 Correct 319 ms 2804 KB Output is correct
5 Correct 406 ms 2804 KB Output is correct