| 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 | ||||