2802021-06-22 15:26:31mraronJáték a síkoncpp14Accepted 100/100326ms4724 KiB
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=3.1415926535897932384626433832795;
const ll INF = 1LL<<62;
const ll MINF = -1LL<<62;

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)

const int MAXN=5001;
int par[MAXN], banned=0;
vector<int> adj[MAXN];
vector<int> comp;
vector<int> color[2];
int st0[MAXN], st1[MAXN];

void dfs0(int x, int c=0) {
    st0[x]=1;
    comp.pb(x);
    color[c].pb(x);
    for(auto i:adj[x]) if(!st0[i]) dfs0(i,c^1);
}

int matching = 0;

bool dfs1(int x) {
    st1[x]=1;
    for(auto i:adj[x]) {
        if(!st1[i] && i!=banned) {
		    if(par[i]==0 || (par[i]!=x && !st1[par[i]] && dfs1(par[i]))) {
				if(par[i]==0) matching++;

				par[x]=i;
				par[i]=x;
                return true;
            }
        }
    }
    return false;
}

int match(bool early=false) {
    bool done_smth;
    do {
        for(int i:comp) {
            st1[i]=0;
        }
    
        done_smth=false;
        for(int i:color[0]) {
            if(i!=banned && !st1[i] && par[i]==0) {
                done_smth|=dfs1(i);
				if(done_smth && early) break ;
            }
        }
    }while(done_smth);
        
    return matching;
}

vector<int> answer(int ind) {
    if(st0[ind]) return {};
    color[0].clear();
    color[1].clear();

    comp.clear();

    dfs0(ind);
	if(sz(color[0])>sz(color[1])) color[0].swap(color[1]);

    for(int i:comp) {
        par[i]=0;
    }
    
    int max_matching=match();
    vector<int> ans;

    for(int i:comp) {
        banned=i;
        
        if(par[banned]) {
            par[par[banned]]=0;
            par[banned]=0;
			matching--;
        }

        int matching=match(true);
        if(matching==max_matching) ans.pb(i);
    }
    
    return ans;
}

int main() {
	IO;
    int n;
    cin>>n;
    vector<pair<int,int>> t(n);
    map<pair<int,int>, int> conv;
    for(int i=0;i<n;++i) {
        cin>>t[i].xx>>t[i].yy;
        conv[t[i]]=i+1;
    }
    
    for(int i=0;i<n;++i) {
        pair<int,int> pt1={t[i].xx+1, t[i].yy};
        pair<int,int> pt2={t[i].xx, t[i].yy+1};
        if(conv.count(pt1)) {
            adj[conv[pt1]].pb(i+1);
            adj[i+1].pb(conv[pt1]);
        }

        if(conv.count(pt2)) {
            adj[conv[pt2]].pb(i+1);
            adj[i+1].pb(conv[pt2]);
        }
    }
    
    vector<int> ans;
    for(int i=1;i<=n;++i) {
        for(auto j:answer(i)) ans.pb(j);
    }
    
    cout<<sz(ans)<<"\n";
    for(auto i:ans) cout<<t[i-1].xx<<" "<<t[i-1].yy<<"\n";
    
	return 0;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms2012 KiB
2Accepted8ms2460 KiB
subtask29/9
3Accepted2ms2108 KiB
4Accepted1ms2112 KiB
subtask310/10
5Accepted1ms2116 KiB
6Accepted1ms2120 KiB
7Accepted1ms2132 KiB
8Accepted1ms2132 KiB
9Accepted1ms2140 KiB
10Accepted2ms2140 KiB
11Accepted1ms2144 KiB
12Accepted1ms2152 KiB
subtask410/10
13Accepted2ms2376 KiB
14Accepted2ms2424 KiB
15Accepted2ms2432 KiB
16Accepted3ms2460 KiB
subtask516/16
17Accepted8ms2500 KiB
18Accepted8ms2496 KiB
19Accepted7ms2496 KiB
20Accepted8ms2512 KiB
21Accepted8ms2568 KiB
subtask618/18
22Accepted2ms2500 KiB
23Accepted2ms2536 KiB
24Accepted2ms2548 KiB
25Accepted2ms2552 KiB
26Accepted4ms2588 KiB
subtask737/37
27Accepted4ms3332 KiB
28Accepted4ms3340 KiB
29Accepted149ms4044 KiB
30Accepted104ms4264 KiB
31Accepted129ms4280 KiB
32Accepted7ms3776 KiB
33Accepted13ms3344 KiB
34Accepted14ms3384 KiB
35Accepted10ms3408 KiB
36Accepted7ms3900 KiB
37Accepted13ms4004 KiB
38Accepted8ms3992 KiB
39Accepted188ms4548 KiB
40Accepted259ms4592 KiB
41Accepted86ms4724 KiB
42Accepted326ms4636 KiB