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