10111 | 2024-03-26 23:32:21 | 111 | Játék a síkon | cpp17 | Hibás válasz 10/100 | 582ms | 4380 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 2012 KiB | ||||
2 | Elfogadva | 107ms | 2320 KiB | ||||
subtask2 | 0/9 | ||||||
3 | Hibás válasz | 3ms | 2280 KiB | ||||
4 | Elfogadva | 3ms | 2496 KiB | ||||
subtask3 | 0/10 | ||||||
5 | Elfogadva | 3ms | 2672 KiB | ||||
6 | Elfogadva | 3ms | 2768 KiB | ||||
7 | Elfogadva | 2ms | 2852 KiB | ||||
8 | Hibás válasz | 2ms | 2860 KiB | ||||
9 | Elfogadva | 2ms | 2856 KiB | ||||
10 | Elfogadva | 2ms | 2856 KiB | ||||
11 | Elfogadva | 3ms | 3088 KiB | ||||
12 | Hibás válasz | 3ms | 3436 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Elfogadva | 64ms | 3388 KiB | ||||
14 | Elfogadva | 63ms | 3568 KiB | ||||
15 | Elfogadva | 63ms | 3400 KiB | ||||
16 | Elfogadva | 61ms | 3664 KiB | ||||
subtask5 | 0/16 | ||||||
17 | Hibás válasz | 150ms | 3928 KiB | ||||
18 | Elfogadva | 71ms | 4044 KiB | ||||
19 | Hibás válasz | 93ms | 3976 KiB | ||||
20 | Hibás válasz | 76ms | 4112 KiB | ||||
21 | Elfogadva | 61ms | 4120 KiB | ||||
subtask6 | 0/18 | ||||||
22 | Elfogadva | 71ms | 4292 KiB | ||||
23 | Hibás válasz | 71ms | 4196 KiB | ||||
24 | Hibás válasz | 76ms | 4196 KiB | ||||
25 | Hibás válasz | 75ms | 4264 KiB | ||||
26 | Hibás válasz | 81ms | 4180 KiB | ||||
subtask7 | 0/37 | ||||||
27 | Időlimit túllépés | 582ms | 3376 KiB | ||||
28 | Időlimit túllépés | 580ms | 3440 KiB | ||||
29 | Időlimit túllépés | 564ms | 3688 KiB | ||||
30 | Időlimit túllépés | 552ms | 3792 KiB | ||||
31 | Időlimit túllépés | 564ms | 3816 KiB | ||||
32 | Időlimit túllépés | 556ms | 3796 KiB | ||||
33 | Időlimit túllépés | 569ms | 3400 KiB | ||||
34 | Időlimit túllépés | 521ms | 4372 KiB | ||||
35 | Időlimit túllépés | 552ms | 4380 KiB | ||||
36 | Időlimit túllépés | 560ms | 3724 KiB | ||||
37 | Időlimit túllépés | 577ms | 3704 KiB | ||||
38 | Időlimit túllépés | 560ms | 3776 KiB | ||||
39 | Időlimit túllépés | 569ms | 3924 KiB | ||||
40 | Időlimit túllépés | 564ms | 3864 KiB | ||||
41 | Időlimit túllépés | 549ms | 3812 KiB | ||||
42 | Időlimit túllépés | 552ms | 3784 KiB |