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