101112024-03-26 23:32:21111Játék a síkoncpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2012 KiB
2Elfogadva107ms2320 KiB
subtask20/9
3Hibás válasz3ms2280 KiB
4Elfogadva3ms2496 KiB
subtask30/10
5Elfogadva3ms2672 KiB
6Elfogadva3ms2768 KiB
7Elfogadva2ms2852 KiB
8Hibás válasz2ms2860 KiB
9Elfogadva2ms2856 KiB
10Elfogadva2ms2856 KiB
11Elfogadva3ms3088 KiB
12Hibás válasz3ms3436 KiB
subtask410/10
13Elfogadva64ms3388 KiB
14Elfogadva63ms3568 KiB
15Elfogadva63ms3400 KiB
16Elfogadva61ms3664 KiB
subtask50/16
17Hibás válasz150ms3928 KiB
18Elfogadva71ms4044 KiB
19Hibás válasz93ms3976 KiB
20Hibás válasz76ms4112 KiB
21Elfogadva61ms4120 KiB
subtask60/18
22Elfogadva71ms4292 KiB
23Hibás válasz71ms4196 KiB
24Hibás válasz76ms4196 KiB
25Hibás válasz75ms4264 KiB
26Hibás válasz81ms4180 KiB
subtask70/37
27Időlimit túllépés582ms3376 KiB
28Időlimit túllépés580ms3440 KiB
29Időlimit túllépés564ms3688 KiB
30Időlimit túllépés552ms3792 KiB
31Időlimit túllépés564ms3816 KiB
32Időlimit túllépés556ms3796 KiB
33Időlimit túllépés569ms3400 KiB
34Időlimit túllépés521ms4372 KiB
35Időlimit túllépés552ms4380 KiB
36Időlimit túllépés560ms3724 KiB
37Időlimit túllépés577ms3704 KiB
38Időlimit túllépés560ms3776 KiB
39Időlimit túllépés569ms3924 KiB
40Időlimit túllépés564ms3864 KiB
41Időlimit túllépés549ms3812 KiB
42Időlimit túllépés552ms3784 KiB