#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;
const int MAXN = 1e5+5;
int N, removed;
struct Point {
int i, j;
};
vector<Point> P;
ll answer;
int lineLoc[MAXN];
// 1 = Vert, 2 = Hor
int dir[MAXN];
void solveRec() {
// cout << "solveRec " << answer << endl;
// for (Point& p : P) cout << p.i << ' ' << p.j << endl;
rep(p, 0, sz(P)) {
int i = P[p].i, j = P[p].j;
// Move point up until it reaches the top row or column
while (i != 0 && j != 0) {
int lowI = i & -i;
int lowJ = j & -j;
if (lowI > lowJ) {
j -= lowJ;
} else if (lowJ > lowI) {
i -= lowI;
} else assert(false);
}
if (i == 0 && j == 0) {
assert(false);
} else if (j == 0) {
// while (i != (i&-i)) i -= i&-i;
dir[p] = 1;
lineLoc[p] = i;
} else if (i == 0) {
// while (j != (j&-j)) j -= j&-j;
dir[p] = 2;
lineLoc[p] = j;
}
}
// cout << "dirs" << endl;
// rep(i, 0, sz(P)) cout << dir[i] << ' ' << lineLoc[i] << endl;
// + vert, - hor
int vertCnt = 0, horCnt = 0;
map<int, int> vertLocs, horLocs;
rep(i, 0, sz(P)) {
if (dir[i] == 1) {
vertCnt++;
vertLocs[lineLoc[i]]++;
} else {
horCnt++;
horLocs[lineLoc[i]]++;
}
}
// Which direction to go in?
vector<Point> newP;
if (vertCnt > N / 2) {
// Move towards vert
// Find place to stop
int ignoredCnt = horCnt + removed;
int toStop, cnt = 0;
for (auto& p : vertLocs) {
cnt += p.second;
if (ignoredCnt + cnt > N / 2) {
toStop = p.first;
break;
}
}
answer += (ll) toStop * ignoredCnt;
rep(p, 0, sz(P)) {
if (dir[p] != 1) {
removed++;
continue;
}
if (lineLoc[p] < toStop) {
// Overshot
answer -= lineLoc[p];
answer += toStop - lineLoc[p];
removed++;
} else {
answer -= toStop;
if (lineLoc[p] > toStop) removed++;
else if (P[p].i == toStop && P[p].j == 0) removed++;
else newP.push_back({P[p].i - toStop, P[p].j});
}
}
} else if (horCnt > N / 2) {
// Move towards hor
// Find place to stop
int ignoredCnt = vertCnt + removed;
int toStop, cnt = 0;
for (auto& p : horLocs) {
cnt += p.second;
if (ignoredCnt + cnt > N / 2) {
toStop = p.first;
break;
}
}
answer += (ll) toStop * ignoredCnt;
rep(p, 0, sz(P)) {
if (dir[p] != 2) {
removed++;
continue;
}
if (lineLoc[p] < toStop) {
// Overshot
answer -= lineLoc[p];
answer += toStop - lineLoc[p];
removed++;
} else {
answer -= toStop;
if (lineLoc[p] > toStop) removed++;
else if (P[p].i == 0 && P[p].j == toStop) removed++;
else newP.push_back({P[p].i, P[p].j - toStop});
}
}
} else {
// Don't move
return;
}
P = newP;
solveRec();
}
void solve() {
cin >> N;
rep(i, 0, N) {
int a, b;
cin >> a >> b;
P.push_back({a, b});
}
// Get initial dists
answer = 0, removed = 0;
vector<Point> newP;
rep(p, 0, sz(P)) {
int i = P[p].i, j = P[p].j;
// cout << "on " << i << " " << j << endl;
// Move point up until it reaches the top row or column
while (i != 0 && j != 0) {
int lowI = i & -i;
int lowJ = j & -j;
if (lowI > lowJ) {
j -= lowJ;
answer += lowJ;
} else {
i -= lowI;
answer += lowI;
}
}
answer += i + j;
if (P[p].i == 0 && P[p].j == 0) removed++;
else newP.push_back(P[p]);
}
P = newP;
solveRec();
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
cvenk.cpp: In function 'void solveRec()':
cvenk.cpp:123:17: warning: 'toStop' may be used uninitialized in this function [-Wmaybe-uninitialized]
123 | if (lineLoc[p] > toStop) removed++;
| ^~
cvenk.cpp:93:17: warning: 'toStop' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | if (lineLoc[p] > toStop) removed++;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
2708 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
25 ms |
2764 KB |
Output is correct |
| 4 |
Correct |
23 ms |
2748 KB |
Output is correct |
| 5 |
Correct |
25 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
53 ms |
2784 KB |
Output is correct |
| 3 |
Correct |
55 ms |
5824 KB |
Output is correct |
| 4 |
Correct |
48 ms |
5892 KB |
Output is correct |
| 5 |
Correct |
49 ms |
6180 KB |
Output is correct |
