Submission #1138864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138864		eggx50000	ČVENK (COI15_cvenk)	C++20	60 / 100	771 ms	3564 KiB

cvenk

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <assert.h>
#define int long long
using namespace std;
using ll = long long;
const ll mod = 1000000007;

int n;

struct Da{
    ll x, y;

    bool operator <(const Da &a) const{
        if(x == a.x) return y < a.y;
        else return x < a.x;
    }

    bool operator !=(const Da &a) const{
        return x != a.x || y != a.y;
    }

} arr[1000099], nrr[1000099];

Da f(Da k, ll v){
    if(k.x + k.y <= v) return k;
    for(int i = 0; i <= 32; i ++){
        ll yi = 1;
        yi <<= i;
        if(k.x & yi){
            if(k.x - yi + k.y <= v) return {v - k.y, k.y};
            else k.x -= yi;
        }
        if(k.y & yi){
            if(k.y - yi + k.x <= v) return {k.x, v - k.x};
            else k.y -= yi;
        }
    }
    return k;
}

ll dst(Da kk, Da ko){
    ll s = 0, e = max(kk.x + kk.y, ko.x + ko.y);
    while(s <= e){
        int m = (s + e) / 2;
        if(f(kk, m) != f(ko, m)) e = m - 1;
        else s = m + 1;
    }
    return kk.x + kk.y + ko.x + ko.y - e * 2;
}

signed main()
{
    scanf("%lld", &n);
    ll ma = 0;
    for(int i = 1; i <= n; i ++){
        scanf("%lld %lld", &arr[i].x, &arr[i].y);
        ma = max(ma, arr[i].x + arr[i].y);
    }
    ll s = 0, e = 20000000000;
    while(s <= e){
        ll m = (s + e) / 2;
        for(int i = 1; i <= n; i ++) nrr[i] = f(arr[i], m);
        sort(nrr + 1, nrr + n + 1);
        int yu = 0, mm = 0;
        for(int i = 1; i <= n; i ++){
            if(nrr[i - 1] != nrr[i]) yu = 0;
            yu ++;
            mm = max(mm, yu);
        }
        if(mm * 2 >= n) s = m + 1;
        else e = m - 1;
    }
    for(int i = 1; i <= n; i ++){
        nrr[i] = f(arr[i], e);
        assert((nrr[i].x & nrr[i].y) == 0);
    }
    sort(nrr + 1, nrr + n + 1);
    Da mo;
    int yu = 0;
    for(int i = 1; i <= n; i ++){
        if(nrr[i - 1].x != nrr[i].x) yu = 0;
        yu ++;
        if(yu * 2 >= n){
            mo = nrr[i];
            break;
        }
    }
    assert(n <= 2 || mo.x + mo.y == e);
    ll ret = 0;
    for(int i = 1; i <= n; i ++) ret += dst(mo, arr[i]);
    printf("%lld", ret);
    return 0;
}

Compilation message (stderr)

cvenk.cpp: In function 'int main()':
cvenk.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
cvenk.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%lld %lld", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40