oj.uz

Submission #28615

# Submission time Handle Problem Language Result Execution time Memory
28615 2017-07-16T08:02:44 Z samir_droubi ČVENK (COI15_cvenk) C++14
78 / 100
 3000 ms 2800 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];

int mxlog=0;
void kth(int &x, int &y, int k)
{
    while(k)
    {
        int vlx = (x & -x);
        int vly = (y & -y);
        int t=k;
        if(x) t = min(t, vlx);
        if(y) t = min(t, vly);
        if(!y || (x && vlx < vly ) ) x -= t ;
        else y -= t;
        k -= t;
    }
}
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)
    {
        for(int i = 30 ; 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;
    }

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

Compilation message

cvenk.cpp: In function 'int main()':
cvenk.cpp:103:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
cvenk.cpp:105: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 2800 KB Output is correct
2 Correct 0 ms 2800 KB Output is correct
3 Correct 0 ms 2800 KB Output is correct
4 Correct 0 ms 2800 KB Output is correct

Subtask #2
21.0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2800 KB Output is correct
2 Correct 106 ms 2800 KB Output is correct
3 Correct 46 ms 2800 KB Output is correct
4 Correct 59 ms 2800 KB Output is correct
5 Execution timed out 3000 ms 2800 KB Execution timed out

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 2800 KB Output is correct
2 Correct 736 ms 2800 KB Output is correct
3 Correct 333 ms 2800 KB Output is correct
4 Correct 303 ms 2800 KB Output is correct
5 Correct 403 ms 2800 KB Output is correct