13072022-04-18 19:37:35k_balintJáték a síkoncpp14Wrong answer 0/10041ms4304 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=5005;

int n,tt;
vector<int> adj[c];
int vis[c],par[c];
bool A[c],ans[c];
map<pair<int,int>,int> m;
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
pair<int,int> arr[c];

bool novel(int v){
    if(vis[v]==tt) return 0;
    vis[v]=tt;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if(par[x]==x){
            par[v]=x; par[x]=v;
            return 1;
        }
        else{
            vis[x]=tt;
            if(novel(par[x])){
                par[v]=x; par[x]=v;
            }
        }
    }
    return 0;
}

void magyar(){
    for(int i=1;i<=n;i++) par[i]=i;
    tt=1;
    for(int i=1;i<=n;i++){
        if(A[i] && par[i]==i){
            ++tt; novel(i);
        }
    }
}

void edg(int i){
    for(int j=0;j<4;j++){
        int nx=arr[i].first+xx[j]; int ny=arr[i].second+yy[j];
        auto it=m.find(make_pair(nx,ny));
        if(it!=m.end()){
            adj[i].push_back(it->second);
            adj[it->second].push_back(i);
        }
    }
}

void dfsa(int v){
    vis[v]=tt;
    if(A[v]) ans[v]=1;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if((A[v] && par[v] != x) || (!A[v] && par[v]==x)) dfsa(x);
    }
}

void dfsb(int v){
    vis[v]=tt;
    if(!A[v]) ans[v]=1;
    for(int x:adj[v]){
        if(vis[x]==tt) continue;
        if((!A[v]&&par[v]!=x)|| (A[v]&&par[v]!=x)) dfsb(x);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        arr[i]=make_pair(a,b);
        m[arr[i]]=i; edg(i);
        A[i]=(a+b)&1;
    }

    magyar();

    for(int i=1;i<=n;i++){
        if(par[i]==i){
            ++tt;
            if(A[i]) dfsa(i);
            else dfsb(i);
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++) {
        if(ans[i]) ++cnt;
    }
    cout << cnt << '\n';
    for(int i=1;i<=n;i++){
        if(ans[i]) cout << arr[i].first << ' ' << arr[i].second << '\n';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms2152 KiB
2Wrong answer3ms2376 KiB
subtask20/9
3Wrong answer1ms2200 KiB
4Accepted1ms2208 KiB
subtask30/10
5Accepted1ms2204 KiB
6Accepted2ms2212 KiB
7Accepted1ms2216 KiB
8Wrong answer1ms2224 KiB
9Wrong answer1ms2224 KiB
10Wrong answer1ms2228 KiB
11Accepted1ms2232 KiB
12Accepted1ms2240 KiB
subtask40/10
13Accepted2ms2460 KiB
14Wrong answer2ms2500 KiB
15Wrong answer2ms2520 KiB
16Wrong answer2ms2520 KiB
subtask50/16
17Wrong answer2ms2536 KiB
18Wrong answer2ms2544 KiB
19Wrong answer2ms2556 KiB
20Wrong answer2ms2588 KiB
21Accepted2ms2584 KiB
subtask60/18
22Accepted2ms2576 KiB
23Wrong answer2ms2620 KiB
24Wrong answer2ms2632 KiB
25Wrong answer2ms2628 KiB
26Wrong answer3ms2656 KiB
subtask70/37
27Wrong answer6ms3368 KiB
28Accepted4ms3328 KiB
29Wrong answer10ms3688 KiB
30Wrong answer41ms3728 KiB
31Wrong answer12ms3788 KiB
32Wrong answer6ms3684 KiB
33Wrong answer7ms3180 KiB
34Wrong answer8ms3204 KiB
35Wrong answer8ms3224 KiB
36Wrong answer6ms3808 KiB
37Wrong answer9ms3996 KiB
38Wrong answer7ms4044 KiB
39Wrong answer13ms4128 KiB
40Wrong answer12ms4180 KiB
41Wrong answer17ms4228 KiB
42Wrong answer20ms4304 KiB