#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
int dx[8] = {0, -1, 0, 1, -1, -1, 1, 1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};
const int N = 2005;
bool vis[N], vis2[N * 9];
bool check(vector<array<int, 3>> a) {
if (a.empty()) {
return 1;
}
for (int i = 0; i < SZ(a); i++) {
vis[i] = 0;
}
queue<int> q;
q.push(0);
int cnt = 0;
vis[0] = 1;
cnt++;
auto getp = [&] (int x, int y) {
return lower_bound(a.begin(), a.end(), (array<int, 3>) {x, y, -1}) - a.begin();
};
while (SZ(q)) {
int i = q.front();
int x = a[i][0], y = a[i][1];
q.pop();
for (int k = 0; k < 8; k++) {
int newx = x + dx[k], newy = y + dy[k];
int p = getp(newx, newy);
if (p < SZ(a) && a[p][0] == newx && a[p][1] == newy && !vis[p]) {
q.push(p);
vis[p] = 1;
cnt++;
}
}
}
return cnt == SZ(a);
}
vector<int> adj[N];
bool art[N], vis3[N];
int low[N], t[N], curt;
void dfs(int i, int p) {
t[i] = low[i] = curt++;
vis3[i] = 1;
int cnt = 0;
for (auto nxt : adj[i]) {
if (nxt == p) continue;
if (vis3[nxt]) {
low[i] = min(low[i], t[nxt]);
} else {
dfs(nxt, i);
low[i] = min(low[i], low[nxt]);
if (low[nxt] >= t[i]) {
cnt++;
}
}
}
if (cnt > 1 || (i != p && cnt)) {
art[i] = 1;
}
}
vector<array<int, 2>> gud;
array<int, 2> compressed[N];
int idx[3 * N][3 * N];
int marked[3 * N][3 * N];
vector<int> vals[2];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
int type;
cin >> type;
vector<array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
a[i][2] = i;
for (int k = 0; k < 2; k++) {
vals[k].push_back(a[i][k]);
vals[k].push_back(a[i][k] - 1);
vals[k].push_back(a[i][k] + 1);
}
}
sort(a.begin(), a.end());
if (!check(a)) {
cout << "NO\n";
return 0;
}
for (int k = 0; k < 2; k++) {
sort(vals[k].begin(), vals[k].end());
vals[k].resize(unique(vals[k].begin(), vals[k].end()) - vals[k].begin());
}
auto getcord = [&] (int x, int y) {
int vx = lower_bound(vals[0].begin(), vals[0].end(), x) - vals[0].begin();
int vy = lower_bound(vals[1].begin(), vals[1].end(), y) - vals[1].begin();
return (array<int, 2>) {vx, vy};
};
memset(idx, -1, sizeof idx);
memset(marked, -1, sizeof marked);
for (int i = 0; i < n; i++) {
array<int, 2> cord = getcord(a[i][0], a[i][1]);
compressed[a[i][2]] = cord;
idx[cord[0]][cord[1]] = a[i][2];
}
vector<int> ans;
while (SZ(ans) < n) {
gud.clear();
int pos[n]{};
memset(pos, -1, sizeof pos);
for (int i = 0; i < SZ(a); i++) {
pos[a[i][2]] = i;
}
for (int i = 0; i < SZ(a); i++) {
for (int k = 0; k < 8; k++) {
gud.push_back({compressed[a[i][2]][0] + dx[k], compressed[a[i][2]][1] + dy[k]});
}
}
array<int, 3> mn = {(int) 1e9 + 5, -1, -1};
for (int k = 0; k < SZ(gud); k++) {
vis2[k] = 0;
mn = min(mn, (array<int, 3>) {gud[k][0], gud[k][1], k});
marked[gud[k][0]][gud[k][1]] = k;
}
queue<int> q;
q.push(mn[2]);
vis2[mn[2]] = 1;
while (SZ(q)) {
int i = q.front();
int x = gud[i][0], y = gud[i][1];
q.pop();
for (int k = 0; k < 4; k++) {
int newx = x + dx[k], newy = y + dy[k];
int nxt = -1;
if (0 <= newx && newx < SZ(vals[0]) && 0 <= newy && newy < SZ(vals[1])) {
if (vals[0][newx] - vals[0][x] == dx[k] && vals[1][newy] - vals[1][y] == dy[k]) {
if (idx[newx][newy] == -1 || pos[idx[newx][newy]] == -1) {
nxt = marked[newx][newy];
}
}
}
if (nxt != -1) {
q.push(nxt);
vis2[nxt] = 1;
}
}
}
for (int i = 0; i < SZ(a); i++) {
adj[i].clear();
art[i] = 0;
vis3[i] = 0;
}
for (int i = 0; i < SZ(a); i++) {
int x = compressed[a[i][2]][0], y = compressed[a[i][2]][1];
for (int k = 0; k < 8; k++) {
int newx = x + dx[k], newy = y + dy[k];
if (idx[newx][newy] != -1 && pos[idx[newx][newy]] != -1) {
adj[i].push_back(pos[idx[newx][newy]]);
}
}
}
curt = 0;
dfs(0, 0);
array<int, 2> mx = {-1, -1};
for (int i = 0; i < SZ(a); i++) {
bool ok = 0;
for (int k = 0; k < 4; k++) {
int x = a[i][0] + dx[k], y = a[i][1] + dy[k];
if (marked[x][y] != -1) ok |= vis2[marked[x][y]];
}
if (ok && !art[i]) {
mx = max(mx, {a[i][2], i});
}
}
assert(mx[0] != -1);
ans.push_back(mx[0]);
vector<array<int, 3>> newa;
for (int j = 0; j < SZ(a); j++) {
if (j == mx[1]) continue;
newa.push_back(a[j]);
}
a = newa;
for (auto [x, y] : gud) {
marked[x][y] = -1;
}
}
cout << "YES\n";
reverse(ans.begin(), ans.end());
for (auto i : ans) {
cout << i + 1 << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2927 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2927 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2927 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
604 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
2716 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2927 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
7876 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
604 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
2716 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
