Submission #410548

#TimeUsernameProblemLanguageResultExecution timeMemory
410548GiantpizzaheadČVENK (COI15_cvenk)C++11
0 / 100
569 ms8124 KiB
#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]; // 0 = On top, 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 (true) { int lowI = i & -i; int lowJ = j & -j; if (lowI == 0 && lowJ == 0) { dir[p] = 0; lineLoc[p] = 0; break; } else if (lowJ == 0) { if (i == lowI) { dir[p] = 1; lineLoc[p] = i; break; } else i -= lowI; } else if (lowI == 0) { if (j == lowJ) { dir[p] = 2; lineLoc[p] = j; break; } else j -= lowJ; } else if (lowI > lowJ) { j -= lowJ; } else if (lowJ > lowI) { i -= lowI; } } } cout << "dirs" << endl; rep(i, 0, sz(P)) cout << dir[i] << ' ' << lineLoc[i] << endl; // + vert, 0 at, - hor int zeroCnt = 0, vertCnt = 0, horCnt = 0; map<int, int> vertLocs, horLocs; rep(i, 0, sz(P)) { if (dir[i] == 0) zeroCnt++; else 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 = zeroCnt + horCnt + removed; int toStop = 0, 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; newP.push_back({P[p].i - toStop, P[p].j}); } } } else if (horCnt > N / 2) { // Move towards hor // Find place to stop int ignoredCnt = zeroCnt + vertCnt + removed; int toStop = 0, 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; 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; 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 && lowJ != 0) || (lowI == 0)) { j -= lowJ; answer += lowJ; } else { i -= lowI; answer += lowI; } } } removed = 0; solveRec(); cout << answer << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...