#include <bits/stdc++.h>
using namespace std;
int n;
pair<int,int> arr[100005];
pair<int,int> adj[2][100005];
vector<int> al[100005];
struct node{
int s,e,m,v;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;v=0;
if(s!=e){l=new node(s,m);r=new node(m+1,e);}
}
void upd(int x,int add){
if(s==e){v+=add;return;}
if(x<=m)l->upd(x,add);
else r->upd(x,add);
v=l->v+r->v;
}
int qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return l->qry(x,m)+r->qry(m+1,y);
}
}*root; //point modify range sum query
bool poss(vector<pair<int,int> > v){
//check whether the connections here intersect (false) or not (true)
vector<pair<int,int> > hor,ver[100005];
for(int i=0;i<(int)v.size();i++){
if(arr[v[i].first].first==arr[v[i].second].first){
ver[arr[v[i].first].first].push_back(make_pair(arr[v[i].first].second,arr[v[i].second].second));
}else{
int a=arr[v[i].first].first,b=arr[v[i].second].first;
if(a>b)swap(a,b);
hor.push_back(make_pair(a,arr[v[i].first].second));hor.push_back(make_pair(b,-arr[v[i].second].second));
}
}
sort(hor.begin(),hor.end());
root=new node(0,100005);
int ptr=0;
for(int i=0;i<100005;i++){
while(ptr<(int)hor.size()&&hor[ptr].first<=i){
if(hor[ptr].second>0)root->upd(hor[ptr].second,1);
else root->upd(-hor[ptr].second,-1);
ptr++;
}
for(int j=0;j<(int)ver[i].size();j++){
int a=ver[i][j].first,b=ver[i][j].second;
if(a>b)swap(a,b);
if(root->qry(a,b)>0){
return false;
}
}
}
return true;
}
int main(){
scanf("%d",&n);
for(int i=0;i<100005;i++)adj[0][i]=adj[1][i]=make_pair(-1,-1);
for(int i=0;i<n;i++){
scanf("%d%d",&arr[i].first,&arr[i].second);
if(adj[0][arr[i].first].first==-1)adj[0][arr[i].first].first=i;
else adj[0][arr[i].first].second=i;
if(adj[1][arr[i].second].first==-1)adj[1][arr[i].second].first=i;
else adj[1][arr[i].second].second=i;
}
for(int i=0;i<n;i++){
if(adj[0][arr[i].first].second==-1&&adj[1][arr[i].second].second==-1){ //no friends
printf("NE");return 0;
}
if(adj[0][arr[i].first].second!=-1){ //vertical friend
if(adj[0][arr[i].first].first==i)al[i].push_back(adj[0][arr[i].first].second);
else al[i].push_back(adj[0][arr[i].first].first);
}
if(adj[1][arr[i].second].second!=-1){ //horizontal friend
if(adj[1][arr[i].second].first==i)al[i].push_back(adj[1][arr[i].second].second);
else al[i].push_back(adj[1][arr[i].second].first);
}
//draw directed edges, the other direction will be drawn by the other person
}
//for(int i=0;i<n;i++){for(int j=0;j<(int)al[i].size();j++)printf("%d ",al[i][j]);printf("\n");}
vector<pair<int,int> > ans;
//consider "forced" friends (degree 1)
queue<int> q;
for(int i=0;i<n;i++){
if((int)al[i].size()==1)q.push(i);
}
while(!q.empty()){
int cur=q.front();q.pop();
for(int i=0;i<(int)al[cur].size();i++){ //1 or 0
int x=al[cur][i];
if((int)al[x].size()==2){
if(al[x][0]==cur){
al[x][0]=al[x][1];
}
al[x].pop_back(); //get rid of cur from x friend list
ans.push_back(make_pair(cur,x));
//now x not allowed to have friends anymore
int y=al[x][0];
if((int)al[y].size()==1){
printf("NE"); return 0;
//y has no friends because x is friends with cur
}else{
assert((int)al[y].size()==2);
if(al[y][0]==x)al[y][0]=al[y][1];
al[y].pop_back();
q.push(y); //push cur's friend's friend into the queue
}
}else if((int)al[x].size()==1){
ans.push_back(make_pair(cur,x));
}
al[x].clear();
}
al[cur].clear();
}
//for(int i=0;i<n;i++){for(int j=0;j<(int)al[i].size();j++)printf("%d ",al[i][j]);printf("\n");}
//everything left in al is degree 2, connect these in one direction
vector<pair<int,int> > ans2;for(int i=0;i<(int)ans.size();i++)ans2.push_back(ans[i]);
//ans is vertical, ans2 is horizontal. need to check whether things intersect at the end
for(int i=0;i<n;i++){
if((int)al[i].size()==0)continue;
assert((int)al[i].size()==2);
if(arr[al[i][0]].first==arr[i].first&&al[i][0]<i){
ans.push_back(make_pair(al[i][0],i));
}else if(arr[al[i][1]].first==arr[i].first&&al[i][1]<i){
ans.push_back(make_pair(al[i][1],i));
}
if(arr[al[i][0]].second==arr[i].second&&al[i][0]<i){
ans2.push_back(make_pair(al[i][0],i));
}else if(arr[al[i][1]].second==arr[i].second&&al[i][1]<i){
ans2.push_back(make_pair(al[i][1],i));
}
}
if(poss(ans)){
if(n>40)return 1;
printf("DA\n");
for(int i=0;i<(int)ans.size();i++){
printf("%d %d\n",ans[i].first+1,ans[i].second+1);
}
}else if(poss(ans2)){
if(n>40)return 2;
printf("DA\n");
for(int i=0;i<(int)ans2.size();i++){
printf("%d %d\n",ans2[i].first+1,ans2[i].second+1);
}
}else{
printf("NE");
}
}
Compilation message
matching.cpp: In function 'int main()':
matching.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
matching.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&arr[i].first,&arr[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16000 KB |
Output is correct |
| 4 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 6 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 7 |
Correct |
28 ms |
25344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16000 KB |
Output is correct |
| 4 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 6 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 7 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 9 |
Correct |
27 ms |
25344 KB |
Output is correct |
| 10 |
Correct |
28 ms |
25336 KB |
Output is correct |
| 11 |
Correct |
30 ms |
25472 KB |
Output is correct |
| 12 |
Correct |
18 ms |
16000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16000 KB |
Output is correct |
| 4 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 6 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 7 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 9 |
Correct |
27 ms |
25344 KB |
Output is correct |
| 10 |
Correct |
28 ms |
25336 KB |
Output is correct |
| 11 |
Correct |
30 ms |
25472 KB |
Output is correct |
| 12 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 13 |
Incorrect |
29 ms |
25472 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16000 KB |
Output is correct |
| 4 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 6 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 7 |
Correct |
28 ms |
25344 KB |
Output is correct |
| 8 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 9 |
Correct |
27 ms |
25344 KB |
Output is correct |
| 10 |
Correct |
28 ms |
25336 KB |
Output is correct |
| 11 |
Correct |
30 ms |
25472 KB |
Output is correct |
| 12 |
Correct |
18 ms |
16000 KB |
Output is correct |
| 13 |
Incorrect |
29 ms |
25472 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
