13092022-04-18 19:47:08k_balintJáték a síkoncpp14Elfogadva 100/10018ms4300 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms2148 KiB
2Elfogadva3ms2380 KiB
subtask29/9
3Elfogadva1ms2224 KiB
4Elfogadva1ms2236 KiB
subtask310/10
5Elfogadva1ms2244 KiB
6Elfogadva1ms2248 KiB
7Elfogadva1ms2256 KiB
8Elfogadva1ms2252 KiB
9Elfogadva1ms2248 KiB
10Elfogadva1ms2260 KiB
11Elfogadva1ms2264 KiB
12Elfogadva1ms2268 KiB
subtask410/10
13Elfogadva2ms2380 KiB
14Elfogadva2ms2400 KiB
15Elfogadva2ms2420 KiB
16Elfogadva2ms2572 KiB
subtask516/16
17Elfogadva2ms2572 KiB
18Elfogadva2ms2576 KiB
19Elfogadva2ms2592 KiB
20Elfogadva2ms2620 KiB
21Elfogadva2ms2500 KiB
subtask618/18
22Elfogadva2ms2492 KiB
23Elfogadva2ms2516 KiB
24Elfogadva2ms2664 KiB
25Elfogadva2ms2672 KiB
26Elfogadva2ms2688 KiB
subtask737/37
27Elfogadva4ms3400 KiB
28Elfogadva4ms3344 KiB
29Elfogadva14ms3704 KiB
30Elfogadva18ms3792 KiB
31Elfogadva16ms3860 KiB
32Elfogadva4ms3788 KiB
33Elfogadva4ms3256 KiB
34Elfogadva8ms3280 KiB
35Elfogadva8ms3272 KiB
36Elfogadva6ms3936 KiB
37Elfogadva8ms4000 KiB
38Elfogadva6ms4072 KiB
39Elfogadva8ms4172 KiB
40Elfogadva8ms4188 KiB
41Elfogadva8ms4284 KiB
42Elfogadva12ms4300 KiB