제출 #242883

#제출 시각아이디문제언어결과실행 시간메모리
242883kingfran1907ČVENK (COI15_cvenk)C++14
17 / 100
459 ms3424 KiB
#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 != t2) { 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; }

컴파일 시 표준 에러 (stderr) 메시지

cvenk.cpp: In function 'llint solve(int, int)':
cvenk.cpp:89:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     if (x & (y + 1) == 0 && 2 * cnt(x, y + 1) >= n) return -1;
             ~~~~~~~~^~~~
cvenk.cpp:90:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     if ((x + 1) & y == 0 && 2 * cnt(x + 1, y) >= n) return -1;
                   ~~^~~~
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...