101112024-03-26 23:32:21111Játék a síkoncpp17Wrong answer 10/100582ms4380 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>& a, vector<int>& b, int x) {
	vector<int> v(g.size());
	auto dfs = [&](auto self, int i) {
		if (v[i] || a[i] == -2) {
			return 0;
		}
		v[i] = 1;
		for (int j : g[i]) {
			if (b[j] == -1 || self(self, b[j])) {
				b[j] = i;
				a[i] = j;
				return 1;
			}
		}
		return 0;
	};
	return dfs(dfs, x);
}

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>a(p,-1),aa(N-p,-1);
	vector<int>b(N-p,-1),bb(p,-1);
	for(int i=0;i<p;i++){
		kuhn(g,a,b,i);
	}
	for(int i=0;i<N-p;i++){
		kuhn(gg,aa,bb,i);
	}
	int c=p-count(a.begin(),a.end(),-1);
	int cc=N-p-count(aa.begin(),aa.end(),-1);
	vector<int>ans;
	for(int i=0;i<p;i++){
		fill(a.begin(),a.end(),-1);
		fill(b.begin(),b.end(),-1);
		a[i]=-2;
		for(int i=0;i<p;i++){
			kuhn(g,a,b,i);
		}
		if(p-count(a.begin(),a.end(),-1)-1==c){
			ans.push_back(i);
		}
	}
	for(int i=0;i<N-p;i++){
		fill(aa.begin(),aa.end(),-1);
		fill(bb.begin(),bb.end(),-1);
		aa[i]=-2;
		for(int i=0;i<N-p;i++){
			kuhn(gg,aa,bb,i);
		}
		if(N-p-count(aa.begin(),aa.end(),-1)-1==cc){
			ans.push_back(p+i);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<v[i].x<<' '<<v[i].y<<'\n';
	}
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2012 KiB
2Accepted107ms2320 KiB
subtask20/9
3Wrong answer3ms2280 KiB
4Accepted3ms2496 KiB
subtask30/10
5Accepted3ms2672 KiB
6Accepted3ms2768 KiB
7Accepted2ms2852 KiB
8Wrong answer2ms2860 KiB
9Accepted2ms2856 KiB
10Accepted2ms2856 KiB
11Accepted3ms3088 KiB
12Wrong answer3ms3436 KiB
subtask410/10
13Accepted64ms3388 KiB
14Accepted63ms3568 KiB
15Accepted63ms3400 KiB
16Accepted61ms3664 KiB
subtask50/16
17Wrong answer150ms3928 KiB
18Accepted71ms4044 KiB
19Wrong answer93ms3976 KiB
20Wrong answer76ms4112 KiB
21Accepted61ms4120 KiB
subtask60/18
22Accepted71ms4292 KiB
23Wrong answer71ms4196 KiB
24Wrong answer76ms4196 KiB
25Wrong answer75ms4264 KiB
26Wrong answer81ms4180 KiB
subtask70/37
27Time limit exceeded582ms3376 KiB
28Time limit exceeded580ms3440 KiB
29Time limit exceeded564ms3688 KiB
30Time limit exceeded552ms3792 KiB
31Time limit exceeded564ms3816 KiB
32Time limit exceeded556ms3796 KiB
33Time limit exceeded569ms3400 KiB
34Time limit exceeded521ms4372 KiB
35Time limit exceeded552ms4380 KiB
36Time limit exceeded560ms3724 KiB
37Time limit exceeded577ms3704 KiB
38Time limit exceeded560ms3776 KiB
39Time limit exceeded569ms3924 KiB
40Time limit exceeded564ms3864 KiB
41Time limit exceeded549ms3812 KiB
42Time limit exceeded552ms3784 KiB