12862022-03-30 10:16:47Valaki2Játék a síkoncpp14Time limit exceeded 45/100597ms2760 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> > points;
vector<vector<int> > adj;

vector<bool> vis;

bool wins(int cur) {
    vis[cur] = true;
    bool result = true;
    for(int nei : adj[cur]) {
        if(!vis[nei]) {
            if(wins(nei)) {
                result = false;
            }
        }
    }
    vis[cur] = false;
    return result;
}

void solve() {
    cin >> n;
    points.assign(n, mp(0, 0));
    adj.assign(n, vector<int> (0, 0));
    for(int i = 0; i < n; i++) {
        cin >> points[i].fi >> points[i].se;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(abs(points[i].fi - points[j].fi) + abs(points[i].se - points[j].se) == 1) {
                adj[i].pb(j);
            }
        }
    }
    vector<pair<int, int> > ans;
    vis.assign(n, false);
    for(int i = 0; i < n; i++) {
        if(wins(i)) {
            ans.pb(points[i]);
        }
    }
    cout << (int) ans.size() << "\n";
    for(pair<int, int> p : ans) {
        cout << p.fi << " " << p.se << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1820 KiB
2Time limit exceeded527ms2020 KiB
subtask29/9
3Accepted1ms1876 KiB
4Accepted1ms1880 KiB
subtask310/10
5Accepted1ms1904 KiB
6Accepted1ms1888 KiB
7Accepted1ms1896 KiB
8Accepted2ms1908 KiB
9Accepted1ms1912 KiB
10Accepted1ms1932 KiB
11Accepted1ms1928 KiB
12Accepted1ms1916 KiB
subtask410/10
13Accepted4ms2040 KiB
14Accepted4ms2028 KiB
15Accepted4ms2100 KiB
16Accepted4ms2144 KiB
subtask516/16
17Accepted17ms2220 KiB
18Accepted17ms2192 KiB
19Accepted17ms2196 KiB
20Accepted17ms2212 KiB
21Accepted18ms2308 KiB
subtask60/18
22Accepted4ms2156 KiB
23Accepted4ms2132 KiB
24Accepted4ms2152 KiB
25Accepted10ms2240 KiB
26Time limit exceeded513ms1232 KiB
subtask70/37
27Accepted68ms2732 KiB
28Accepted71ms2760 KiB
29Time limit exceeded517ms1820 KiB
30Time limit exceeded517ms1664 KiB
31Time limit exceeded509ms1860 KiB
32Time limit exceeded513ms1828 KiB
33Time limit exceeded584ms1580 KiB
34Time limit exceeded565ms1784 KiB
35Time limit exceeded578ms1800 KiB
36Time limit exceeded588ms1820 KiB
37Time limit exceeded586ms1868 KiB
38Time limit exceeded582ms1980 KiB
39Time limit exceeded596ms2072 KiB
40Time limit exceeded597ms2184 KiB
41Time limit exceeded565ms2240 KiB
42Time limit exceeded575ms2304 KiB