#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
int grid[2001][2001],vs[2001][2001],w[2001][2001];
/*int x[] = {-1,-1,-1,0,1,1,1,0}, y[] = {-1,0,1,1,1,0,-1,-1};*/
int x[] = {0,0,-1,1}, y[] = {1,-1,0,0};
vector<pair<int,int>>p,nxt;
vector<int>ans;
int n, f;
/*bool cmp(int* a, int *b){
return *a < *b;
}
bool check(){
vector<pair<int,int>>b;
b.push_back({p[0].first,p[0].second});
set<pair<int,int>>c,d;
for(int i = 0; i < n; i++){
d.insert({p[i].first,p[i].second});
}
int j = 0;
while(j < b.size()){
for(int k = 0; k < 8; k++){
int nx = b[j].first + x[k], ny = b[j].second + y[k];
if(d.count({nx,ny})){
d.erase({nx,ny});
b.push_back({nx,ny});
}
}
j++;
}
return d.empty();
}
void dfs(int a, int b){
vs[a][b] = 1;
if(grid[a][b]){
nxt.push_back({a,b});
ans.push_back(w[a][b]);
return;
}
for(int k = 0; k < 8; k++){
int aa = a + x[k], bb = b + y[k];
if(aa < 0 || bb < 0 || aa >= n || bb >= n || !grid[aa][bb] || vs[aa][bb]) continue;
dfs(aa,bb);
}
}*/
void dfs(int a, int b){
if(a == 0 || b == 0 || a == n - 1 || b == n - 1){
f = 1;
return;
}
vs[a][b] = 1;
for(int k = 0; k < 4; k++){
int aa = a + x[k], bb = b + y[k];
if(f) return;
if(aa < 0 || bb < 0 || aa >= n || bb >= n || vs[aa][bb] || grid[aa][bb]) continue;
dfs(aa,bb);
}
}
signed main(){
boost;
int t; cin >> n >> t;
vector<pair<int,pair<int,int>>>c;
for(int i = 0; i < n; i++){
int x,y; cin >> x >> y;
c.push_back({x,{y,i}});
}
sort(c.begin(), c.end());
do{
int x = c[0].first, y = c[0].second.first, no = 0;
vs[x][y] = 1;
grid[x][y] = 1;
for(int i = 1; i < n; i++){
if(abs(c[i].first - x) > 1 || abs(y - c[i].second.first) > 1){
no = 1;
}
if(no) break;
dfs(c[i].first,c[i].second.first);
if(!f) no = 1;
f = 0;
if(no) break;
x = c[i].first; y = c[i].second.first;
}
if(!no){
cout << "YES" << endl;
for(int i = 0; i < n; i++){
cout << c[i].second.second + 1 << endl;
}
return 0;
}
for(int i = 0; i < n ;i++){
for(int j = 0; j < n; j++) {
grid[i][j] = vs[i][j] = 0;
}
}
}while(next_permutation(c.begin(), c.end()));
cout << "NO";
/*vector<int*>d;
for(int i = 0; i < n; i++){
int x,y;
cin >> x >> y;
p.push_back({x,y});
d.push_back(&p[i].first);
d.push_back(&p[i].second);
}
if(!check()){
cout << "NO";
return 0;
}
sort(d.begin(), d.end(),cmp);
int cur = -1, prev = 0;
for(auto s:d){
if(*s != prev) cur++;
prev = *s;
*s = cur;
}
for(int i = 0; i < n; i++){
grid[p[i].first][p[i].second] = 1;
w[p[i].first][p[i].second] = i;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == 0 || j == 0 || i == n - 1|| j == n - 1) {
if(!vs[i][j]) dfs(i,j);
}
}
}
while(!nxt.empty()){
vector<pair<int,int>>nw = nxt;
nxt.clear();
for(int i = 0; i < nw.size(); i++){
int a = nw[i].first, b = nw[i].second;
for(int k = 0; k < 8; k++){
int aa = a + x[k], bb = b + y[k];
if(aa < 0 || bb < 0 || aa >= n || bb >= n || vs[aa][bb]) continue;
dfs(aa,bb);
}
}
}
cout << "YES" << endl;
for(int i = 0; i < n; i++){
cout << ans[i] + 1 << endl;
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
152 ms |
130880 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
