1287 | 2022-03-30 10:21:29 | Valaki2 | Játék a síkon | cpp14 | Időlimit túllépés 45/100 | 596ms | 2340 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 2ms | 1820 KiB | ||||
2 | Időlimit túllépés | 582ms | 1068 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Elfogadva | 1ms | 1876 KiB | ||||
4 | Elfogadva | 1ms | 1876 KiB | ||||
subtask3 | 10/10 | ||||||
5 | Elfogadva | 1ms | 1880 KiB | ||||
6 | Elfogadva | 1ms | 1884 KiB | ||||
7 | Elfogadva | 1ms | 1888 KiB | ||||
8 | Elfogadva | 1ms | 1896 KiB | ||||
9 | Elfogadva | 1ms | 1900 KiB | ||||
10 | Elfogadva | 1ms | 1904 KiB | ||||
11 | Elfogadva | 1ms | 1908 KiB | ||||
12 | Elfogadva | 2ms | 1916 KiB | ||||
subtask4 | 10/10 | ||||||
13 | Elfogadva | 4ms | 1976 KiB | ||||
14 | Elfogadva | 4ms | 2016 KiB | ||||
15 | Elfogadva | 4ms | 2016 KiB | ||||
16 | Elfogadva | 6ms | 2044 KiB | ||||
subtask5 | 16/16 | ||||||
17 | Elfogadva | 17ms | 2204 KiB | ||||
18 | Elfogadva | 16ms | 2072 KiB | ||||
19 | Elfogadva | 17ms | 2076 KiB | ||||
20 | Elfogadva | 17ms | 2232 KiB | ||||
21 | Elfogadva | 21ms | 2268 KiB | ||||
subtask6 | 0/18 | ||||||
22 | Elfogadva | 4ms | 2092 KiB | ||||
23 | Elfogadva | 4ms | 2128 KiB | ||||
24 | Elfogadva | 4ms | 2136 KiB | ||||
25 | Elfogadva | 9ms | 2144 KiB | ||||
26 | Időlimit túllépés | 596ms | 1208 KiB | ||||
subtask7 | 0/37 | ||||||
27 | Hibás válasz | 1ms | 2088 KiB | ||||
28 | Hibás válasz | 1ms | 2112 KiB | ||||
29 | Hibás válasz | 1ms | 2132 KiB | ||||
30 | Hibás válasz | 1ms | 2144 KiB | ||||
31 | Hibás válasz | 1ms | 2156 KiB | ||||
32 | Hibás válasz | 1ms | 2172 KiB | ||||
33 | Hibás válasz | 1ms | 2196 KiB | ||||
34 | Hibás válasz | 1ms | 2204 KiB | ||||
35 | Hibás válasz | 1ms | 2224 KiB | ||||
36 | Hibás válasz | 1ms | 2236 KiB | ||||
37 | Hibás válasz | 1ms | 2252 KiB | ||||
38 | Hibás válasz | 1ms | 2272 KiB | ||||
39 | Hibás válasz | 1ms | 2284 KiB | ||||
40 | Hibás válasz | 1ms | 2304 KiB | ||||
41 | Hibás válasz | 1ms | 2320 KiB | ||||
42 | Hibás válasz | 1ms | 2340 KiB |