oj.uz

답안 #197736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197736 2020-01-22T16:12:36 Z dolphingarlic ČVENK (COI15_cvenk) C++14
0 / 100
 46 ms 3704 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll tot_dist = 0, ans = LLONG_MAX;
 
struct Node {
    ll x, y, l;
    Node *c[2];
 
    Node(ll X = 0, ll Y = 0): x(X), y(Y), l(0) {
        c[0] = c[1] = NULL;
    }
 
    void insert(Node *ins, int child) {
        l++;
        if (!c[child]) {
            c[child] = ins;
            return;
        }
        if (ins->x < c[child]->x || ins->y < c[child]->y) {
            ins->c[child] = c[child];
            ins->l += c[child]->l;
            c[child] = ins;
        }
    }
};
 
int n;
Node *root = new Node();
 
void dfs(Node *curr) {
    ans = min(ans, tot_dist);
    for (int i = 0; i < 2; i++) {
        if (curr->c[i]) {
            ll dx = curr->x - curr->c[i]->x + curr->y - curr->c[i]->y;
            tot_dist += dx * (2 * curr->c[i]->l - n);
            dfs(curr->c[i]);
            tot_dist -= dx * (2 * curr->c[i]->l - n);
        }
    }
}

pair<ll, ll> a[100000];
bool cmp(pair<ll, ll> x, pair<ll, ll> y) { return x.first + x.second > y.first + y.second; }
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
        tot_dist += a[i].first + a[i].second;
    }
    sort(a, a + n, cmp);

    for (int i = 0; i < n; i++) {
        Node *curr = root;
        ll cx = 0, cy = 0;
        for (int j = 30; ~j; j--) {
            if (a[i].first & (1 << j)) {
                cx |= (1 << j);
                curr->insert(new Node(cx, cy), 0);
                curr = curr->c[0];
            } else if (a[i].second & (1 << j)) {
                cy |= (1 << j);
                curr->insert(new Node(cx, cy), 1);
                curr = curr->c[0];
            }
        }
        curr->l++;
    }
    dfs(root);
    cout << ans;
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 3668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -