1309 2022. 04. 18 19:47:08 k_balint Játék a síkon cpp14 Elfogadva 100/100 18ms 4300 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';
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 2148 KiB
2 Elfogadva 3ms 2380 KiB
subtask2 9/9
3 Elfogadva 1ms 2224 KiB
4 Elfogadva 1ms 2236 KiB
subtask3 10/10
5 Elfogadva 1ms 2244 KiB
6 Elfogadva 1ms 2248 KiB
7 Elfogadva 1ms 2256 KiB
8 Elfogadva 1ms 2252 KiB
9 Elfogadva 1ms 2248 KiB
10 Elfogadva 1ms 2260 KiB
11 Elfogadva 1ms 2264 KiB
12 Elfogadva 1ms 2268 KiB
subtask4 10/10
13 Elfogadva 2ms 2380 KiB
14 Elfogadva 2ms 2400 KiB
15 Elfogadva 2ms 2420 KiB
16 Elfogadva 2ms 2572 KiB
subtask5 16/16
17 Elfogadva 2ms 2572 KiB
18 Elfogadva 2ms 2576 KiB
19 Elfogadva 2ms 2592 KiB
20 Elfogadva 2ms 2620 KiB
21 Elfogadva 2ms 2500 KiB
subtask6 18/18
22 Elfogadva 2ms 2492 KiB
23 Elfogadva 2ms 2516 KiB
24 Elfogadva 2ms 2664 KiB
25 Elfogadva 2ms 2672 KiB
26 Elfogadva 2ms 2688 KiB
subtask7 37/37
27 Elfogadva 4ms 3400 KiB
28 Elfogadva 4ms 3344 KiB
29 Elfogadva 14ms 3704 KiB
30 Elfogadva 18ms 3792 KiB
31 Elfogadva 16ms 3860 KiB
32 Elfogadva 4ms 3788 KiB
33 Elfogadva 4ms 3256 KiB
34 Elfogadva 8ms 3280 KiB
35 Elfogadva 8ms 3272 KiB
36 Elfogadva 6ms 3936 KiB
37 Elfogadva 8ms 4000 KiB
38 Elfogadva 6ms 4072 KiB
39 Elfogadva 8ms 4172 KiB
40 Elfogadva 8ms 4188 KiB
41 Elfogadva 8ms 4284 KiB
42 Elfogadva 12ms 4300 KiB