Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF1237C2 【Balanced Removals (Harder)】

posted on 2019-10-18 10:20:34 | under 题解 |

这么妙的题怎么没人发题解啊

首先这是三维的,我们可以对其进行降维打击

先考虑一维怎么做?

我们可以对其该维坐标进行排序,按照顺序输出,可能会多余一个

那拓展到二维呢?

我们可以把它转化成一维,分成很多个一维后执行上述操作,把一维中多的一些点存下来,可以保证这些点的一维值两两不等,于是按照另一维坐标输出就行了

那三维呢?

其实和二维是一样的,用类似操作转化成二维即可

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 100005
struct node {
    int x, y, z, id;
}e[maxn], p[maxn], q[maxn], a[maxn], b[maxn];
//e用来存储三维坐标,p用来存储第三维相等时的二维坐标,q用来存储第二三维都相等的一维坐标
//a用来存储二维操作中剩余点的坐标,b则是用来存储三位操作中剩余点的坐标
int n, c2D, c3D;
il bool cmp(node a, node b) { return a.z < b.z; }
il bool cmp1(node a, node b) { return a.y < b.y; }
il bool cmp2(node a, node b) {return a.x < b.x; }
il void solve1D(int x) {
    sort(q + 1, q + x + 1, cmp2);
    for(re int i = 1; i < x; i += 2) printf("%d %d\n", q[i].id, q[i + 1].id);
    if(x & 1) a[++ c2D] = q[x];
}
il void solve2D(int x) {
    sort(p + 1, p + x + 1, cmp1);
    int now = 1, cnt = 0; c2D = 0;
    rep(i, 1, x) {
        now = i;
        while(now <= x && p[i].y == p[now].y) q[++ cnt] = p[now ++];
        i = now - 1, solve1D(cnt), cnt = 0;
    }
    for(re int i = 1; i < c2D; i += 2) printf("%d %d\n", a[i].id, a[i + 1].id);
    if(c2D & 1) b[++ c3D] = a[c2D];
}
il void solve3D() {
    sort(e + 1, e + n + 1, cmp);
    int now = 1, cnt = 0;
    rep(i, 1, n) {
        now = i;
        while(now <= n && e[i].z == e[now].z) p[++ cnt] = e[now ++];
        i = now - 1, solve2D(cnt), cnt = 0;
    }
    for(re int i = 1; i < c3D; i += 2) printf("%d %d\n", b[i].id, b[i + 1].id);
}
int main() {
    n = read();
    rep(i, 1, n) e[i].id = i, e[i].x = read(), e[i].y = read(), e[i].z = read();
    solve3D();
    return 0;
}