13042022-04-14 22:06:18Valaki2Játék a síkoncpp14Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1816 KiB
2Elfogadva4ms2028 KiB
subtask29/9
3Elfogadva1ms1868 KiB
4Elfogadva1ms1868 KiB
subtask310/10
5Elfogadva1ms1880 KiB
6Elfogadva1ms1876 KiB
7Elfogadva1ms1880 KiB
8Elfogadva1ms1884 KiB
9Elfogadva1ms1892 KiB
10Elfogadva1ms1900 KiB
11Elfogadva1ms1900 KiB
12Elfogadva1ms1900 KiB
subtask410/10
13Elfogadva3ms1964 KiB
14Elfogadva4ms2008 KiB
15Elfogadva3ms2012 KiB
16Elfogadva3ms2032 KiB
subtask516/16
17Elfogadva3ms2188 KiB
18Elfogadva3ms2060 KiB
19Elfogadva4ms2068 KiB
20Elfogadva3ms2080 KiB
21Elfogadva3ms2256 KiB
subtask618/18
22Elfogadva3ms2080 KiB
23Elfogadva4ms2120 KiB
24Elfogadva3ms2124 KiB
25Elfogadva4ms2140 KiB
26Elfogadva4ms2168 KiB
subtask737/37
27Elfogadva45ms2616 KiB
28Elfogadva46ms2620 KiB
29Elfogadva48ms3184 KiB
30Elfogadva59ms3292 KiB
31Elfogadva59ms3336 KiB
32Elfogadva46ms3048 KiB
33Elfogadva12ms2840 KiB
34Elfogadva10ms2872 KiB
35Elfogadva9ms2880 KiB
36Elfogadva46ms3236 KiB
37Elfogadva48ms3264 KiB
38Elfogadva46ms3264 KiB
39Elfogadva52ms3600 KiB
40Elfogadva56ms3688 KiB
41Elfogadva59ms3884 KiB
42Elfogadva52ms3772 KiB