#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 100;
int x[N], y[N];
int lx[N], ly[N];
vector<pii> T[N];
int ea[N], eb[N];
int cl[N], cr[N];
int com[N];
int typ[N];
int c;
int n;
int pi, qi;
vector<pii> curs;
struct SegTree{
set<pii> T[N * 4 + 512];
void add(int node, int cl, int cr, int tl, int tr, pii v, int ki){
if(cr < tl)
return;
if(cl > tr)
return;
if(cl >= tl && cr <= tr){
if(ki)
T[node].insert(v);
else{
T[node].erase(v);
}
return;
}
int mid = (cl + cr) / 2;
add(node * 2, cl, mid, tl, tr, v, ki);
add(node * 2 + 1, mid + 1, cr, tl, tr, v, ki);
}
void qry(int node, int cl, int cr, int pos, int tl, int tr){
auto it = T[node].lower_bound(mp(tl,-1));
while(it != T[node].end()){
if((it->fi) > tr) break;
curs.push_back(*it);
it ++ ;
}
if(cl == cr)
return;
int mid = (cl + cr) / 2;
if(mid >= pos){
qry(node * 2, cl, mid, pos, tl, tr);
}
else{
qry(node * 2, mid + 1, cr, pos, tl, tr);
}
}
};
int cp;
vector<int> id[N][2];
bool vis[N];
int idx[N];
int ks;
void dfs(int u, int pr){
vis[u]=true;
ks ++ ;
for(auto x : T[u]){
if(x.fi == pr) continue;
id[cp][typ[x.se]].push_back(x.se);
idx[x.se]=cp;
if(!vis[x.fi]){
dfs(x.fi,u);
break;
}
}
}
SegTree pck[2], nt[2];
int tsz[2];
bool use[N];
queue<int> bf;
void add_to_queue(int edg){
pck[typ[edg]].add(1, 0, n - 1, cl[edg], cr[edg],mp(com[edg], edg), 1);
bf.push(edg);
use[edg]=true;
}
int main(){
fastIO;
cin >> n;
vector<int> xc, yc;
for(int i = 1; i <= n; i ++ ){
cin >> x[i] >> y[i];
xc.push_back(x[i]);
yc.push_back(y[i]);
}
sort(xc.begin(),xc.end());
sort(yc.begin(),yc.end());
xc.resize(unique(xc.begin(),xc.end())-xc.begin());
yc.resize(unique(yc.begin(),yc.end())-yc.begin());
for(int i = 1; i <= n; i ++ ){
x[i]=lower_bound(xc.begin(),xc.end(),x[i])-xc.begin();
y[i]=lower_bound(yc.begin(),yc.end(),y[i])-yc.begin();
}
for(int i = 1; i <= n; i ++ ){
if(lx[x[i]] == 0){
lx[x[i]]=i;
}
else{
c ++ ;
ea[c] = lx[x[i]];
eb[c] = i;
com[c]=x[i];
cl[c]=y[i];
cr[c]=y[lx[x[i]]];
typ[c]=0;
T[lx[x[i]]].push_back(mp(i,c));
T[i].push_back(mp(lx[x[i]],c));
}
if(ly[y[i]] == 0){
ly[y[i]]=i;
}
else{
c++;
ea[c]=ly[y[i]];
eb[c]=i;
com[c]=y[i];
cl[c]=x[i];
cr[c]=x[ly[y[i]]];
typ[c]=1;
T[ly[y[i]]].push_back(mp(i, c));
T[i].push_back(mp(ly[y[i]], c));
}
}
for(int i = 1; i <= c; i ++ ){
if(cl[i] > cr[i])
swap(cl[i],cr[i]);
}
for(int i = 1; i <= n; i ++ ){
if(!vis[i]){
cp++;
ks=0;
dfs(i,-1);
if(ks % 2 == 1){
cout << "NE\n";
return 0;
}
if(id[cp][0].size() + id[cp][1].size() == ks){
for(auto x : id[cp][0]){
nt[0].add(1, 0, n-1, cl[x], cr[x], mp(com[x], x), 1);
}
for(auto x : id[cp][1]){
nt[1].add(1, 0, n-1, cl[x], cr[x], mp(com[x], x), 1);
}
}
else{
if(id[cp][0].size() > id[cp][1].size()){
for(auto x : id[cp][0]) add_to_queue(x);
}
else{
for(auto x : id[cp][1]) add_to_queue(x);
}
id[cp][0].clear();
id[cp][1].clear();
}
}
}
int node;
int rev;
int cur;
while(!bf.empty()){
node=bf.front();
bf.pop();
curs.clear();
cur = typ[node];
rev = typ[node]^1;
pck[rev].qry(1, 0, n - 1, com[node], cl[node],cr[node]);
if(!curs.empty()){
cout << "NE\n";
return 0;
}
nt[rev].qry(1, 0, n - 1, com[node], cl[node], cr[node]);
for(auto p : curs){
if(id[idx[p.se]][cur].empty()) continue;
for(auto x : id[idx[p.se]][cur]){
add_to_queue(x);
nt[cur].add(1, 0, n - 1, cl[x], cr[x], mp(com[x],x), 0);
}
for(auto x : id[idx[p.se]][rev]){
nt[rev].add(1, 0, n - 1, cl[x], cr[x], mp(com[x],x), 0);
}
id[idx[p.se]][0].clear();
id[idx[p.se]][1].clear();
}
}
for(int i = 1; i <= cp; i ++ ){
for(auto x : id[i][0]){
use[x]=true;
}
}
cout << "DA\n";
for(int i = 1; i <= c; i ++ )
if(use[i])
cout << ea[i] << " " << eb[i] << "\n";
return 0;
}
Compilation message
matching.cpp: In function 'int main()':
matching.cpp:159:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(id[cp][0].size() + id[cp][1].size() == ks){
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
82808 KB |
Output is correct |
| 2 |
Correct |
51 ms |
82808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
82808 KB |
Output is correct |
| 2 |
Correct |
51 ms |
82808 KB |
Output is correct |
| 3 |
Correct |
48 ms |
82816 KB |
Output is correct |
| 4 |
Correct |
49 ms |
82816 KB |
Output is correct |
| 5 |
Correct |
49 ms |
82808 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
82808 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
82808 KB |
Output is correct |
| 2 |
Correct |
51 ms |
82808 KB |
Output is correct |
| 3 |
Correct |
48 ms |
82816 KB |
Output is correct |
| 4 |
Correct |
49 ms |
82816 KB |
Output is correct |
| 5 |
Correct |
49 ms |
82808 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
82808 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
82808 KB |
Output is correct |
| 2 |
Correct |
51 ms |
82808 KB |
Output is correct |
| 3 |
Correct |
48 ms |
82816 KB |
Output is correct |
| 4 |
Correct |
49 ms |
82816 KB |
Output is correct |
| 5 |
Correct |
49 ms |
82808 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
82808 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
82808 KB |
Output is correct |
| 2 |
Correct |
51 ms |
82808 KB |
Output is correct |
| 3 |
Correct |
48 ms |
82816 KB |
Output is correct |
| 4 |
Correct |
49 ms |
82816 KB |
Output is correct |
| 5 |
Correct |
49 ms |
82808 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
82808 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
