#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define pi3 pair<pii,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define MP3(a,b,c) MP(MP(a,b),c)
using namespace std;
typedef long long ll;
const int md = int(1e9) + 7;
const int N = 100100;
const int PW = 20;
const int oo = 2e9;
set<pii> ste;
vector<pii> res;
vector<pi3> vec[2];
vector<int> vc, vx[N], vy[N];
int n, x[N], y[N], sosed_x[N], sosed_y[N], kol[N];
bool mrk[N], fd = 0;
pii loc;
void BAD(){
cout << "NE";
exit(0);
}
struct seg_tree{
vector<pii> vec;
vector<pii> tree;
seg_tree(): vec(0), tree(0) {}
void build(int v, int l, int r){
if (l == r) {
tree[v] = MP(vec[l].sd, vec[l].ft);
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
tree[v] = max(tree[v + v], tree[v + v + 1]);
}
pii get(int v, int l, int r, int lht, int rht){
if (lht > vec[r].ft || rht < vec[l].ft) return MP(-oo, -oo);
if (vec[l].ft >= lht && vec[r].ft <= rht)
return tree[v];
int md = (l + r) >> 1;
return max(get(v + v, l, md, lht, rht),
get(v + v + 1, md + 1, r, lht, rht));
}
void update(int v, int l, int r, pii cur){
if (l == r){
tree[v] = MP(-oo, -oo);
return;
}
int md = (l + r) >> 1;
if (cur <= vec[md])
update(v + v, l, md, cur);
else update(v + v + 1, md + 1, r, cur);
tree[v] = max(tree[v + v], tree[v + v + 1]);
}
};
seg_tree st[2][4 * N];
void build(int tp, int v, int l, int r){
if (l == r){
st[tp][v].vec.clear();
st[tp][v].vec.PB(MP(vec[tp][l].sd, vec[tp][l].ft.sd));
st[tp][v].tree.resize(2);
st[tp][v].tree[1] = MP(vec[tp][l].ft.sd, vec[tp][l].sd);
return;
}
int md = (l + r) >> 1;
build(tp, v + v, l, md);
build(tp, v + v + 1, md + 1, r);
merge(all(st[tp][v + v].vec), all(st[tp][v + v + 1].vec), back_inserter(st[tp][v].vec));
st[tp][v].tree.resize(sz(st[tp][v].vec) + 3);
st[tp][v].build(1, 0, sz(st[tp][v].vec) - 1);
}
void search(int tp, int v, int l, int r, int lht, int rht, int vl){
if (fd) return;
if (vec[tp][l].ft.ft > vl) return;
if (vec[tp][r].ft.ft <= vl){
pii mem = st[tp][v].get(1, 0, sz(st[tp][v].vec) - 1, lht, rht);
if (mem.ft >= vl){
fd = 1;
loc = mem;
}
return;
}
int md = (l + r) >> 1;
search(tp, v + v, l, md, lht, rht, vl);
search(tp, v + v + 1, md + 1, r, lht, rht, vl);
}
void update(int tp, int v, int l, int r, pi3 cur){
st[tp][v].update(1, 0, sz(st[tp][v].vec) - 1, MP(cur.sd, cur.ft.sd));
if (l == r) return;
int md = (l + r) >> 1;
if (cur <= vec[tp][md])
update(tp, v + v, l, md, cur);
else update(tp, v + v + 1, md + 1, r, cur);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n;
vc.clear();
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
vc.PB(x[i]);
sosed_x[i] = sosed_y[i] = -1;
}
sort(all(vc));
vc.resize(unique(all(vc)) - vc.begin());
for (int i = 0; i < n; i++)
x[i] = lower_bound(all(vc), x[i]) - vc.begin();
vc.clear();
for (int i = 0; i < n; i++)
vc.PB(y[i]);
sort(all(vc));
vc.resize(unique(all(vc)) - vc.begin());
for (int i = 0; i < n; i++)
y[i] = lower_bound(all(vc), y[i]) - vc.begin();
for (int i = 0; i < n; i++){
vx[x[i]].PB(i);
vy[y[i]].PB(i);
}
for (int i = 0; i < n; i++){
if (sz(vx[i]) == 2){
sosed_x[vx[i][0]] = vx[i][1];
sosed_x[vx[i][1]] = vx[i][0];
kol[vx[i][0]]++;
kol[vx[i][1]]++;
int lf = min(y[vx[i][0]], y[vx[i][1]]);
int rt = max(y[vx[i][0]], y[vx[i][1]]);
vec[0].PB(MP3(lf, rt, i));
}
if (sz(vy[i]) == 2){
sosed_y[vy[i][0]] = vy[i][1];
sosed_y[vy[i][1]] = vy[i][0];
kol[vy[i][0]]++;
kol[vy[i][1]]++;
int lf = min(x[vy[i][0]], x[vy[i][1]]);
int rt = max(x[vy[i][0]], x[vy[i][1]]);
vec[1].PB(MP3(lf, rt, i));
}
}
for (int i = 0; i < n; i++)
ste.insert(MP(kol[i], i));
for (int tp = 0; tp < 2; tp++){
if (!sz(vec[tp])) continue;
sort(all(vec[tp]));
build(tp, 1, 0, sz(vec[tp]) - 1);
}
while (sz(ste)){
int v = (*ste.begin()).sd;
ste.erase(ste.begin());
mrk[v] = 1;
if (kol[v] == 0)
BAD();
if (kol[v] == 2){
for (int i = 0; i < n; i++)
if (!mrk[i]){
mrk[i] = 1;
mrk[sosed_x[i]] = 1;
res.PB(MP(i, sosed_x[i]));
}
break;
}
if (sosed_x[v] >= 0){
int u = sosed_x[v];
mrk[u] = 1;
res.PB(MP(u, v));
ste.erase(MP(kol[u], u));
int rbd = max(y[u], y[v]);
int lbd = min(y[u], y[v]);
while (1){
fd = 0;
if (!sz(vec[1])) break;
search(1, 1, 0, sz(vec[1]) - 1, lbd, rbd, x[v]);
if (!fd) break;
int lf = loc.sd;
int n1 = vy[lf][0], n2 = vy[lf][1];
int le = min(x[n1], x[n2]);
int ri = max(x[n1], x[n2]);
if (le <= x[v] && ri >= x[v]){
ste.erase(MP(kol[n1], n1));
ste.erase(MP(kol[n2], n2));
kol[n1]--;
kol[n2]--;
if (!mrk[n1]) ste.insert(MP(kol[n1], n1));
if (!mrk[n2]) ste.insert(MP(kol[n2], n2));
vy[lf].clear();
sosed_y[n1] = -1;
sosed_y[n2] = -1;
}
update(1, 1, 0, sz(vec[1]) - 1, MP3(le, ri, loc.sd));
}
} else {
int u = sosed_y[v];
mrk[u] = 1;
res.PB(MP(u, v));
ste.erase(MP(kol[u], u));
int rbd = max(x[u], x[v]);
int lbd = min(x[u], x[v]);
while (1){
fd = 0;
if (!sz(vec[0])) break;
search(0, 1, 0, sz(vec[0]) - 1, lbd, rbd, y[v]);
if (!fd) break;
int lf = loc.sd;
int n1 = vx[lf][0], n2 = vx[lf][1];
int le = min(y[n1], y[n2]);
int ri = max(y[n1], y[n2]);
if (le <= y[v] && ri >= y[v]){
ste.erase(MP(kol[n1], n1));
ste.erase(MP(kol[n2], n2));
kol[n1]--;
kol[n2]--;
if (!mrk[n1]) ste.insert(MP(kol[n1], n1));
if (!mrk[n2]) ste.insert(MP(kol[n2], n2));
vx[lf].clear();
sosed_x[n1] = -1;
sosed_x[n2] = -1;
}
update(0, 1, 0, sz(vec[0]) - 1, MP3(le, ri, loc.sd));
}
}
}
cout << "DA\n";
for (pii cr : res)
cout << cr.ft + 1 << " " << cr.sd + 1 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
86392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
86392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
86392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
86392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
86392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
