Submission #410556

#	Time	Username	Problem	Language	Result	Execution time	Memory
410556		Giantpizzahead	ČVENK (COI15_cvenk)	C++11	100 / 100	56 ms	6180 KiB

cvenk

#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 (stderr)

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++;
      |                 ^~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40