13042022-04-14 22:06:18Valaki2Játék a síkoncpp14Accepted 100/10059ms3884 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int n;
vector<pair<int, int> > coords;
vector<vector<int> > g;
vector<bool> A;
vector<bool> B;
vector<bool> vis;
vector<int> pr;
vector<bool> win;

void get_parties(int cur, bool which) {
    if(which) {
        A[cur] = true;
    } else {
        B[cur] = true;
    }
    vis[cur] = true;
    for(int nei : g[cur]) {
        if(!vis[nei]) {
            get_parties(nei, !which);
        }
    }
}

bool dfs(int a) {
    if(vis[a]) {
        return false;
    }
    vis[a] = true;
    for(int b : g[a]) {
        if(pr[b] == -1 || dfs(pr[b])) {
            pr[b] = a;
            pr[a] = b;
            return true;
        }
    }
    return false;
}

void win_a(int cur) {
    if(vis[cur]) {
        return;
    }
    vis[cur] = true;
    if(A[cur]) {
        win[cur] = true;
    }
    for(int nei : g[cur]) {
        if((A[cur] && pr[cur] != nei) || (B[cur] && pr[cur] == nei)) {
            win_a(nei);
        }
    }
}

void win_b(int cur) {
    if(vis[cur]) {
        return;
    }
    vis[cur] = true;
    if(B[cur]) {
        win[cur] = true;
    }
    for(int nei : g[cur]) {
        if((B[cur] && pr[cur] != nei) || (A[cur] && pr[cur] == nei)) {
            win_b(nei);
        }
    }
}

void solve() {
    cin >> n;
    coords.assign(1 + n, mp(0, 0));
    for(int i = 1; i <= n; i++) {
        cin >> coords[i].fi >> coords[i].se;
    }
    g.resize(1 + n);
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(abs(coords[i].fi - coords[j].fi) + abs(coords[i].se - coords[j].se) == 1) {
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    A.assign(1 + n, false);
    B.assign(1 + n, false);
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            get_parties(i, 0);
        }
    }
    pr.assign(1 + n, -1);
    for(int i = 1; i <= n; i++) {
        if(A[i]) {
            vis.assign(1 + n, false);
            dfs(i);
        }
    }
    win.assign(1 + n, false);
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(A[i] && pr[i] == -1) {
            win_a(i);
        }
    }
    vis.assign(1 + n, false);
    for(int i = 1; i <= n; i++) {
        if(B[i] && pr[i] == -1) {
            win_b(i);
        }
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(win[i]) {
            ans.pb(i);
        }
    }
    cout << (int) ans.size() << "\n";
    for(int cur : ans) {
        cout << coords[cur].fi << " " << coords[cur].se << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1816 KiB
2Accepted4ms2028 KiB
subtask29/9
3Accepted1ms1868 KiB
4Accepted1ms1868 KiB
subtask310/10
5Accepted1ms1880 KiB
6Accepted1ms1876 KiB
7Accepted1ms1880 KiB
8Accepted1ms1884 KiB
9Accepted1ms1892 KiB
10Accepted1ms1900 KiB
11Accepted1ms1900 KiB
12Accepted1ms1900 KiB
subtask410/10
13Accepted3ms1964 KiB
14Accepted4ms2008 KiB
15Accepted3ms2012 KiB
16Accepted3ms2032 KiB
subtask516/16
17Accepted3ms2188 KiB
18Accepted3ms2060 KiB
19Accepted4ms2068 KiB
20Accepted3ms2080 KiB
21Accepted3ms2256 KiB
subtask618/18
22Accepted3ms2080 KiB
23Accepted4ms2120 KiB
24Accepted3ms2124 KiB
25Accepted4ms2140 KiB
26Accepted4ms2168 KiB
subtask737/37
27Accepted45ms2616 KiB
28Accepted46ms2620 KiB
29Accepted48ms3184 KiB
30Accepted59ms3292 KiB
31Accepted59ms3336 KiB
32Accepted46ms3048 KiB
33Accepted12ms2840 KiB
34Accepted10ms2872 KiB
35Accepted9ms2880 KiB
36Accepted46ms3236 KiB
37Accepted48ms3264 KiB
38Accepted46ms3264 KiB
39Accepted52ms3600 KiB
40Accepted56ms3688 KiB
41Accepted59ms3884 KiB
42Accepted52ms3772 KiB