1286 | 2022-03-30 10:16:47 | Valaki2 | Játék a síkon | cpp14 | Time limit exceeded 45/100 | 597ms | 2760 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 2ms | 1820 KiB | ||||
2 | Time limit exceeded | 527ms | 2020 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Accepted | 1ms | 1876 KiB | ||||
4 | Accepted | 1ms | 1880 KiB | ||||
subtask3 | 10/10 | ||||||
5 | Accepted | 1ms | 1904 KiB | ||||
6 | Accepted | 1ms | 1888 KiB | ||||
7 | Accepted | 1ms | 1896 KiB | ||||
8 | Accepted | 2ms | 1908 KiB | ||||
9 | Accepted | 1ms | 1912 KiB | ||||
10 | Accepted | 1ms | 1932 KiB | ||||
11 | Accepted | 1ms | 1928 KiB | ||||
12 | Accepted | 1ms | 1916 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Accepted | 4ms | 2040 KiB | ||||
14 | Accepted | 4ms | 2028 KiB | ||||
15 | Accepted | 4ms | 2100 KiB | ||||
16 | Accepted | 4ms | 2144 KiB | ||||
subtask5 | 16/16 | ||||||
17 | Accepted | 17ms | 2220 KiB | ||||
18 | Accepted | 17ms | 2192 KiB | ||||
19 | Accepted | 17ms | 2196 KiB | ||||
20 | Accepted | 17ms | 2212 KiB | ||||
21 | Accepted | 18ms | 2308 KiB | ||||
subtask6 | 0/18 | ||||||
22 | Accepted | 4ms | 2156 KiB | ||||
23 | Accepted | 4ms | 2132 KiB | ||||
24 | Accepted | 4ms | 2152 KiB | ||||
25 | Accepted | 10ms | 2240 KiB | ||||
26 | Time limit exceeded | 513ms | 1232 KiB | ||||
subtask7 | 0/37 | ||||||
27 | Accepted | 68ms | 2732 KiB | ||||
28 | Accepted | 71ms | 2760 KiB | ||||
29 | Time limit exceeded | 517ms | 1820 KiB | ||||
30 | Time limit exceeded | 517ms | 1664 KiB | ||||
31 | Time limit exceeded | 509ms | 1860 KiB | ||||
32 | Time limit exceeded | 513ms | 1828 KiB | ||||
33 | Time limit exceeded | 584ms | 1580 KiB | ||||
34 | Time limit exceeded | 565ms | 1784 KiB | ||||
35 | Time limit exceeded | 578ms | 1800 KiB | ||||
36 | Time limit exceeded | 588ms | 1820 KiB | ||||
37 | Time limit exceeded | 586ms | 1868 KiB | ||||
38 | Time limit exceeded | 582ms | 1980 KiB | ||||
39 | Time limit exceeded | 596ms | 2072 KiB | ||||
40 | Time limit exceeded | 597ms | 2184 KiB | ||||
41 | Time limit exceeded | 565ms | 2240 KiB | ||||
42 | Time limit exceeded | 575ms | 2304 KiB |