#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
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);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
113 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
52 ms |
1664 KB |
Output is correct |
| 4 |
Correct |
49 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
70 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1387 ms |
1536 KB |
Output is correct |
| 2 |
Correct |
489 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
155 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
170 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
221 ms |
1656 KB |
Output is correct |
