Submission #242929

#	Time	Username	Problem	Language	Result	Execution time	Memory
242929		kingfran1907	ČVENK (COI15_cvenk)	C++14	100 / 100	1387 ms	2048 KiB

cvenk

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e5+10;
const int logo = 30;

int n;
int x[maxn], y[maxn];
int v[maxn];

inline int lb(int x) {
    return x & -x;
}

pair<int, int> lif(int x, int y, int k) {
    if (k >= x + y) return make_pair(0, 0);
    while (k > 0) {
        int tren = k;
        if (x > 0) tren = min(tren, lb(x));
        if (y > 0) tren = min(tren, lb(y));

        if (y == 0 || (x > 0 && lb(x) < lb(y))) x -= tren;
        else y -= tren;
        k -= tren;
    }
    return make_pair(x, y);
}

int cnt(int x, int y) {
    int out = 0;
    for (int i = 0; i < n; i++) {
        int del = ::x[i] + ::y[i] - x - y;
        if (del < 0) continue;

        pair<int, int> tr = lif(::x[i], ::y[i], del);
        if (tr.X == x && tr.Y == y) out++;
    }
    return out;
}

pair<int, int> lca(int x1, int y1, int x2, int y2) {
    if (x1 + y1 > x2 + y2) {
        int del = x1 + y1 - x2 - y2;
        pair<int, int> tren = lif(x1, y1, del);

        x1 = tren.X, y1 = tren.Y;
    }
    if (x2 + y2 > x1 + y1) {
        int del = x2 + y2 - x1 - y1;
        pair<int, int> tren = lif(x2, y2, del);

        x2 = tren.X, y2 = tren.Y;
    }
    if (x1 == x2 && y1 == y2) return make_pair(x1, y1);

    for (int i = logo; i >= 0; i--) {
        pair<int, int> t1 = lif(x1, y1, (1 << i));
        pair<int, int> t2 = lif(x2, y2, (1 << i));

        if (t1.X != t2.X || t1.Y != t2.Y) {
            x1 = t1.X, y1 = t1.Y;
            x2 = t2.X, y2 = t2.Y;
        }
    }
    return lif(x1, y1, 1);
}

llint dist(int x1, int y1, int x2, int y2) {
    pair<int, int> lc = lca(x1, y1, x2, y2);
    //printf("debug (%d %d) (%d %d) -> %d %d\n", x1, y1, x2, y2, lc.X, lc.Y);
    return (llint)x1 + x2 + y1 + y2 - 2LL * (lc.X + lc.Y);
}

llint solve(int x, int y) {
    if (cnt(x, y) * 2 < n) {
        for (int i = logo; i >= 0; i--) {
            pair<int, int> tren = lif(x, y, (1 << i));
            int tx = tren.X, ty = tren.Y;
            if (cnt(tx, ty) * 2 < n) x = tx, y = ty;
        }
        pair<int, int> tren = lif(x, y, 1);
        x = tren.X, y = tren.Y;
    }

    if ((x & (y + 1)) == 0 && 2 * cnt(x, y + 1) >= n) return -1;
    if (((x + 1) & y) == 0 && 2 * cnt(x + 1, y) >= n) return -1;

    llint out = 0;
    for (int i = 0; i < n; i++) out += dist(x, y, ::x[i], ::y[i]);
    return out;
}

int main() {
    srand(time(0));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", x+i, y+i);

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

    for (int i = 0; i < n; i++) v[i] = i;
    random_shuffle(v, v+n);

    for (int i = 0; i < n; i++) {
        int tren = v[i];
        llint out = solve(x[tren], y[tren]);
        if (out != -1) {
            printf("%lld\n", out);
            break;
        }
    }
    return 0;
}

Compilation message (stderr)

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

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