이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<ll, ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010
int n;
vector<ii> A;
void clean(ii &a, ii &b) {
for (int i = 30; ~i; i--) {
if ((a.f & (1 << i)) && (b.f & (1 << i))) {
a.f ^= (1 << i);
b.f ^= (1 << i);
} else if ((a.s & (1 << i)) && (b.s & (1 << i))) {
a.s ^= (1 << i);
b.s ^= (1 << i);
} else if ((a.f & (1 << i)) || (b.f & (1 << i)) || (a.s & (1 << i)) || (b.s & (1 << i))) {
break;
}
}
}
// true if left, false if up
// second number is distance from that axis
pair<bool, ll> calc(ii x) {
int dir = -1;
ll dist = 0;
for (int i = 30; ~i; i--) {
int curDir = -1;
if (x.f & (1 << i)) {
curDir = 1;
} else if (x.s & (1 << i)) {
curDir = 0;
}
if (dir == -1) dir = curDir;
if (curDir != -1 && curDir != dir) break;
if (curDir != -1) dist += (1 << i);
}
return make_pair(dir, dist);
}
ll solveSimple(ii a, ii b) {
clean(a, b);
pair<bool, ll> res = calc(a), res2 = calc(b);
ll ans = a.f+a.s+b.f+b.s;
if (res.f == res2.f) {
ans -= 2*min(res.s, res2.s);
}
return ans;
}
int ctr = 1;
struct node {
node *down = nullptr, *right = nullptr, *stay = nullptr;
ll numNodes = 0, moveUpCost = 0;
int id = 0;
int cost = 0;
string path = "";
} root;
ll getMoveUpCost(ii x, int i) {
ll c = 0;
while (i >= 0) {
if ((x.f & (1 << i)) || (x.s & (1 << i))) c += (1 << i);
i--;
}
return c;
}
void add(ii x, int i, node *n) {
n->cost = 1 << (i+1);
n->numNodes++;
if (i < 0) return;
node *next = nullptr;
if (x.f & (1 << i)) {
if (n->down == nullptr) {
n->down = new node;
n->down->id = ctr++;
n->down->path = n->path + "D";
}
next = n->down;
} else if (x.s & (1 << i)) {
if (n->right == nullptr) {
n->right = new node;
n->right->id = ctr++;
n->right->path = n->path + "R";
}
next = n->right;
} else {
if (n->stay == nullptr) {
n->stay = new node;
n->stay->id = ctr++;
n->stay->path = n->path + "S";
}
next = n->stay;
}
next->moveUpCost += getMoveUpCost(x, i);
add(x, i-1, next);
}
ll solve(node *x) {
string path = x->path;
ll ans = 0;
ii y = make_pair(0, 0);
for (int i = 0; i < 31; i++) {
char c = i >= sz(path) ? 'S' : path[i];
if (c == 'D') {
y.f += (1 << (30-i));
} else if (c == 'R') {
y.s += (1 << (30-i));
}
}
for (auto x : A) {
ans += solveSimple(x, y);
}
return ans;
}
ll dp(node *x) {
ll best = solve(x);
if (x->down) {
best = min(best, dp(x->down));
}
if (x->right) {
best = min(best, dp(x->right));
}
if (x->stay) {
best = min(best, dp(x->stay));
}
return best;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
A.resize(n);
F0R(i, n) cin >> A[i].f >> A[i].s;
for (auto x : A) add(x, 30, &root);
cout << dp(&root) << endl;
return 0;
}
# | 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... |