Submission #410543

#	Time	Username	Problem	Language	Result	Execution time	Memory
410543		Giantpizzahead	ČVENK (COI15_cvenk)	C++11	0 / 100	3083 ms	2816 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];
// 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) {
                dir[p] = 1;
                lineLoc[p] = i;
                break;
            } else if (lowI == 0) {
                dir[p] = 2;
                lineLoc[p] = j;
                break;
            } 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;
        // 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;
}

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