101152024-03-27 00:09:44111Játék a síkoncpp17Időlimit túllépés 10/100600ms5308 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct P{
	int x,y;
};

bool kuhn(vector<vector<int>>& g, vector<int>& b, int i) {
	vector<int> v(g.size());
	auto dfs = [&](auto self, int i) {
		if (v[i]) {
			return 0;
		}
		v[i] = 1;
		for (int j : g[i]) {
			if (b[j] == -2) {
				continue;
			}
			if (b[j] == -1 || self(self, b[j])) {
				b[j] = i;
				return 1;
			}
		}
		return 0;
	};
	return dfs(dfs, i);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<P>v(N);
	for(int i=0;i<N;i++){
		cin>>v[i].x>>v[i].y;
	}
	int p=partition(v.begin(),v.end(),[&](P p){return p.x%2==p.y%2;})-v.begin();
	vector<vector<int>>g(p),gg(N-p);
	for(int i=0;i<p;i++){
		for(int j=p;j<N;j++){
			if(abs(v[j].x-v[i].x)+abs(v[j].y-v[i].y)==1){
				g[i].push_back(j-p);
				gg[j-p].push_back(i);
			}
		}
	}
	vector<int>b(N-p,-1),bb(p,-1);
	for(int i=0;i<p;i++){
		kuhn(g,b,i);
	}
	for(int i=0;i<N-p;i++){
		kuhn(gg,bb,i);
	}
	vector<int>ans;
	for(int i=0;i<N-p;i++){
		if(b[i]==-1){
			ans.push_back(p+i);
			continue;
		}
		int x=b[i];
		b[i]=-2;
		if(kuhn(g,b,x)){
			ans.push_back(p+i);
			b[i]=-1;
		}
		else{
			b[i]=x;
		}
	}
	for(int i=0;i<p;i++){
		if(bb[i]==-1){
			ans.push_back(i);
			continue;
		}
		int x=bb[i];
		bb[i]=-2;
		if(kuhn(gg,bb,x)){
			ans.push_back(i);
			bb[i]=-1;
		}
		else{
			bb[i]=x;
		}
	}
	if(1){
		vector<int>ans1;
		vector<vector<int>>g(N);
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(abs(v[j].x-v[i].x)+abs(v[j].y-v[i].y)==1){
					g[i].push_back(j);
				}
			}
		}
		vector<int>w(N);
		auto bt=[&](auto self,int i)->int{
			if(w[i]){
				return 1;
			}
			w[i]=1;
			for(int j:g[i]){
				if(!self(self,j)){
					w[i]=0;
					return 1;
				}
			}
			w[i]=0;
			return 0;
		};
		for(int i=0;i<N;i++){
			if(!bt(bt,i)){
				ans1.push_back(i);
			}
		}
		if(ans.size()!=ans1.size()){
			exit(ans.size()<ans1.size());
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<v[i].x<<' '<<v[i].y<<'\n';
	}
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Időlimit túllépés600ms1580 KiB
subtask20/9
3Hibás válasz3ms2328 KiB
4Elfogadva3ms2444 KiB
subtask30/10
5Elfogadva3ms2656 KiB
6Elfogadva3ms2868 KiB
7Elfogadva3ms2868 KiB
8Futási hiba3ms2884 KiB
9Elfogadva3ms2980 KiB
10Elfogadva3ms3108 KiB
11Elfogadva3ms3208 KiB
12Hibás válasz3ms3424 KiB
subtask410/10
13Elfogadva7ms3708 KiB
14Elfogadva7ms3748 KiB
15Elfogadva7ms3764 KiB
16Elfogadva8ms3764 KiB
subtask50/16
17Hibás válasz10ms4028 KiB
18Elfogadva8ms4088 KiB
19Hibás válasz8ms4200 KiB
20Hibás válasz9ms4292 KiB
21Elfogadva25ms4384 KiB
subtask60/18
22Elfogadva7ms4132 KiB
23Hibás válasz7ms4180 KiB
24Hibás válasz7ms4516 KiB
25Hibás válasz8ms4484 KiB
26Időlimit túllépés546ms4464 KiB
subtask70/37
27Hibás válasz90ms5308 KiB
28Elfogadva90ms5144 KiB
29Időlimit túllépés564ms4152 KiB
30Időlimit túllépés578ms4428 KiB
31Időlimit túllépés546ms4388 KiB
32Időlimit túllépés569ms4360 KiB
33Időlimit túllépés565ms3904 KiB
34Időlimit túllépés578ms3980 KiB
35Időlimit túllépés565ms4240 KiB
36Időlimit túllépés583ms4604 KiB
37Időlimit túllépés550ms4660 KiB
38Időlimit túllépés565ms4676 KiB
39Időlimit túllépés554ms4580 KiB
40Időlimit túllépés549ms4792 KiB
41Időlimit túllépés560ms4920 KiB
42Időlimit túllépés569ms4620 KiB