Balanced Removals (Harder)

Created by LXC on Fri May 19 15:13:38 2023

https://codeforces.com/problemset/problem/1237/C2

ranting: 1900

tag: binary search, constructive algorithms, divide and conquer, greedy, implementation, sortings

题意

给出n个三维平面上的点，n<50000，n为偶数。

每次可以移除两个点，但是这两个点组成的对角线空间（包括空间边界）内不能存在其他点

请构造出移除的序列。

题解

如果n=1000，可以考虑$O(n^2)$做法。
每次任选一个点，然后再移除离这个点欧几里得距离最近的点。
这样做的正确性在于，如果存在其他点在对角线空间则会选取更近的点。

但是$O(n^2)$在本题会超时

我们采取降维分治。

对于同一x值的所有点进行合并，如果是偶数那么所有点会合并完毕，如果是奇数那么会残留一个点。需要合并。

同理对于二维平面上的点也可以由处理一维后合并组成。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define D 3
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(D));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    auto dfs = [&](auto& self, vector<int> idx, int d) {
        if (d == D) {
            return idx[0];
        }
        map<int, vector<int>> mp;
        for (int i : idx) {
            mp[a[i][d]].push_back(i);
        }
        int cnt = 0;
        vector<int> p;
        for (auto& i : mp) {
            int rt = self(self, i.second, d + 1);
            if (rt != -1) {
                p.push_back(rt);
            }
        }
        for (int i = 1; i < p.size(); i += 2) {
            cout << p[i - 1] + 1 << " " << p[i] + 1 << "\n";
        }
        return p.size() % 2 ? p.back() : -1;
    };
    vector<int> idx(n, 0);
    iota(idx.begin(), idx.end(), 0);
    dfs(dfs, idx, 0);
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}