이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,avx2,fma,avx")
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;
}
Node* insert(Node *ins, int child) {
l++;
if (!c[child]) {
c[child] = ins;
return ins;
}
if (ins->x < c[child]->x || ins->y < c[child]->y) {
ins->c[child] = c[child];
ins->l += c[child]->l;
c[child] = ins;
return ins;
}
if (ins->x > c[child]->x || ins->y > c[child]->y)
return c[child]->insert(ins, child);
return c[child];
}
};
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 = curr->insert(new Node(cx, cy), 0);
} else if (a[i].second & (1 << j)) {
cy |= (1 << j);
curr = curr->insert(new Node(cx, cy), 1);
}
}
curr->l++;
}
dfs(root);
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |