Submission #223398

#	Time	Username	Problem	Language	Result	Execution time	Memory
223398		errorgorn	Matching (COCI20_matching)	C++14	58 / 110	2585 ms	14008 KiB

matching

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
 
const int MOD=1000000007;
 
int n;
 
ii pos[100005];
vector<int> X[100005];
vector<int> Y[100005];
 
bool visited[100005];
 
deque<int> stk; //bruh
 
void dfs(int i,bool dir){
	//cout<<i<<" "<<dir<<endl;
	visited[i]=true;
	
	if (dir) stk.push_back(i);
	else stk.push_front(i);
	
	for (auto &it:X[pos[i].first]) if (!visited[it]) dfs(it,dir);
	for (auto &it:Y[pos[i].second]) if (!visited[it]) dfs(it,dir);
}

struct comp{
	vector<ii> ansX;
	vector<ii> ansY;
	
	comp(){}
};

vector<comp> comps; //this is so cancer bruh

vector<int> mono;

vector<ii> ans; //real answer now

bool intersect(ii i,ii j){
	if (pos[i.first].first!=pos[i.second].first) swap(i,j);
	if (pos[i.first].second==pos[i.second].second || pos[j.first].first==pos[j.second].first) return false;
	//cout<<i.first<<" "<<i.second<<" "<<j.first<<" "<<j.second<<endl;
	return min(pos[j.first].first,pos[j.second].first)<=pos[i.first].first &&
			max(pos[j.first].first,pos[j.second].first)>=pos[i.first].first &&
			min(pos[i.first].second,pos[i.second].second)<=pos[j.first].second &&
			max(pos[i.first].second,pos[i.second].second)>=pos[j.first].second;
}
 
int main(){	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	
	int a,b;
	int index=0;
	for (int x=0;x<n;x++){
		cin>>a>>b;
		
		pos[index]=ii(a,b);
		X[a].push_back(index);
		Y[b].push_back(index);
		
		index++;
	}
	
	for (int x=0;x<n;x++){
		if (!visited[x]){
			visited[x]=true;
			stk.clear();
			stk.push_back(x);
			
			for (auto &it:X[pos[x].first]) if (!visited[it]) dfs(it,true);
			for (auto &it:Y[pos[x].second]) if (!visited[it]) dfs(it,false);
			
			if (stk.size()%2==1){
				cout<<"NE"<<endl;
				return 0;
			}
			else{
				comps.push_back(comp());
				if (pos[stk[0]].first==pos[stk[1]].first){
					for (int x=0;x<stk.size();x+=2){
						comps.back().ansX.push_back(ii(stk[x],stk[x+1]));
					}
					if (pos[stk.front()].second==pos[stk.back()].second){
						stk.push_back(stk.front());
						stk.pop_front();
						
						for (int x=0;x<stk.size();x+=2){
							comps.back().ansY.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
				else{
					for (int x=0;x<stk.size();x+=2){
						comps.back().ansY.push_back(ii(stk[x],stk[x+1]));
					}
					if (pos[stk.front()].first==pos[stk.back()].first){
						stk.push_back(stk.front());
						stk.pop_front();
						
						for (int x=0;x<stk.size();x+=2){
							comps.back().ansX.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
			}
		}
	}
	
	/*
	for (auto &it:comps){
		cout<<it.ansX.size()<<" "<<it.ansY.size()<<endl;
	}
	*/
	
	for (int x=0;x<comps.size();x++) {
		if (comps[x].ansX.empty() || comps[x].ansY.empty()) mono.push_back(x);
	}
	
	while (!mono.empty()){
		int index=mono.back();
		mono.pop_back();
		
		for (int x=0;x<comps.size();x++){
			if (!(comps[x].ansX.empty() || comps[x].ansY.empty())){
				if (comps[index].ansX.empty()){
					for (auto &it:comps[index].ansY){
						for (auto &it2:comps[x].ansX){
							if (intersect(it,it2)){
								comps[x].ansX.clear();
								mono.push_back(x);
								goto _end;
							}
						}
					}
				}
				else{
					for (auto &it:comps[index].ansX){
						for (auto &it2:comps[x].ansY){
							if (intersect(it,it2)){
								comps[x].ansY.clear();
								mono.push_back(x);
								goto _end;
							}
						}
					}
				}
				
				_end:;
			}
		}
	}
	
	for (auto &it:comps){
		if (it.ansX.empty()) ans.insert(ans.end(),it.ansY.begin(),it.ansY.end());
		else ans.insert(ans.end(),it.ansX.begin(),it.ansX.end());
	}
	
	for (int x=0;x<ans.size();x++){
		for (int y=0;y<ans.size();y++){
			if (intersect(ans[x],ans[y])){
				cout<<"NE"<<endl;
				return 0;
			}
		}
	}
	
	cout<<"DA"<<endl;
	for (auto &it:ans){
		cout<<it.first+1<<" "<<it.second+1<<endl;
	}
}

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:95:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:108:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<comps.size();x++) {
               ~^~~~~~~~~~~~~
matching.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<comps.size();x++){
                ~^~~~~~~~~~~~~
matching.cpp:166:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<ans.size();x++){
               ~^~~~~~~~~~~
matching.cpp:167:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int y=0;y<ans.size();y++){
                ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52