13082022-04-18 19:44:37k_balintJáték a síkoncpp14Wrong answer 0/10020ms4408 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},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 1;
            }
        }
    }
    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
1Accepted2ms2188 KiB
2Wrong answer3ms2420 KiB
subtask20/9
3Wrong answer1ms2264 KiB
4Accepted1ms2272 KiB
subtask30/10
5Accepted1ms2280 KiB
6Accepted1ms2288 KiB
7Accepted1ms2296 KiB
8Wrong answer1ms2284 KiB
9Accepted1ms2304 KiB
10Accepted1ms2308 KiB
11Accepted1ms2312 KiB
12Accepted1ms2304 KiB
subtask40/10
13Accepted2ms2420 KiB
14Wrong answer2ms2444 KiB
15Wrong answer2ms2560 KiB
16Wrong answer2ms2472 KiB
subtask50/16
17Wrong answer2ms2620 KiB
18Wrong answer2ms2624 KiB
19Wrong answer2ms2500 KiB
20Wrong answer2ms2660 KiB
21Accepted2ms2548 KiB
subtask60/18
22Accepted2ms2532 KiB
23Wrong answer2ms2564 KiB
24Wrong answer2ms2712 KiB
25Wrong answer2ms2588 KiB
26Wrong answer2ms2592 KiB
subtask70/37
27Wrong answer4ms3440 KiB
28Accepted4ms3372 KiB
29Wrong answer14ms3756 KiB
30Wrong answer20ms3984 KiB
31Wrong answer17ms3888 KiB
32Wrong answer4ms3836 KiB
33Wrong answer4ms3284 KiB
34Wrong answer8ms3316 KiB
35Accepted8ms3292 KiB
36Wrong answer6ms3956 KiB
37Wrong answer7ms3984 KiB
38Wrong answer6ms4060 KiB
39Wrong answer8ms4160 KiB
40Wrong answer8ms4236 KiB
41Wrong answer9ms4408 KiB
42Wrong answer10ms4400 KiB