12872022-03-30 10:21:29Valaki2Játék a síkoncpp14Time limit exceeded 45/100596ms2340 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;
    if(n > 1000) {
        return;
    }
    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 exceeded582ms1068 KiB
subtask29/9
3Accepted1ms1876 KiB
4Accepted1ms1876 KiB
subtask310/10
5Accepted1ms1880 KiB
6Accepted1ms1884 KiB
7Accepted1ms1888 KiB
8Accepted1ms1896 KiB
9Accepted1ms1900 KiB
10Accepted1ms1904 KiB
11Accepted1ms1908 KiB
12Accepted2ms1916 KiB
subtask410/10
13Accepted4ms1976 KiB
14Accepted4ms2016 KiB
15Accepted4ms2016 KiB
16Accepted6ms2044 KiB
subtask516/16
17Accepted17ms2204 KiB
18Accepted16ms2072 KiB
19Accepted17ms2076 KiB
20Accepted17ms2232 KiB
21Accepted21ms2268 KiB
subtask60/18
22Accepted4ms2092 KiB
23Accepted4ms2128 KiB
24Accepted4ms2136 KiB
25Accepted9ms2144 KiB
26Time limit exceeded596ms1208 KiB
subtask70/37
27Wrong answer1ms2088 KiB
28Wrong answer1ms2112 KiB
29Wrong answer1ms2132 KiB
30Wrong answer1ms2144 KiB
31Wrong answer1ms2156 KiB
32Wrong answer1ms2172 KiB
33Wrong answer1ms2196 KiB
34Wrong answer1ms2204 KiB
35Wrong answer1ms2224 KiB
36Wrong answer1ms2236 KiB
37Wrong answer1ms2252 KiB
38Wrong answer1ms2272 KiB
39Wrong answer1ms2284 KiB
40Wrong answer1ms2304 KiB
41Wrong answer1ms2320 KiB
42Wrong answer1ms2340 KiB