#include <bits/stdc++.h>
using namespace std;
struct custom_hash{
size_t operator()(pair<long long,long long> x) const{
return x.first*(1e9+5)+x.second;
}
};
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
vector<int> adj[1500];
int v[1500];
int dfs(int x){
v[x]=1;
int ret=1;
for(int i:adj[x]) if(!v[i]) ret+=dfs(i);
return ret;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,t;
cin >> n >> t;
pair<pair<int,int>,int> arr[n];
for(int i=0; i<n; i++){
cin >> arr[i].first.first >> arr[i].first.second;
arr[i].second=i;
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(abs(arr[i].first.first-arr[j].first.first)<=1&&abs(arr[i].first.second-arr[j].first.second)<=1){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
if(dfs(0)!=n){
cout << "NO";
return 0;
}
mt19937 rng(999);
shuffle(arr,arr+n,rng);
do{
bool can=true;
unordered_set<pair<int,int>,custom_hash> got;
for(int i=0; i<n; i++){
bool nxt=false;
if(!i) nxt=true;
for(int j=0; j<i; j++){
if(abs(arr[i].first.first-arr[j].first.first)<=1&&abs(arr[i].first.second-arr[j].first.second)<=1) nxt=true;
}
if(!nxt) can=false;
if(!can) break;
got.clear();
for(int j=0; j<i; j++) got.insert(arr[j].first);
queue<pair<int,int> > q;
q.push(arr[i].first);
while(!q.empty()){
pair<int,int> x=q.front();
q.pop();
if(got.find(x)!=got.end()) continue;
got.insert(x);
if(abs(arr[i].first.first-x.first)+abs(arr[i].first.second-x.second)>n/2) break;
for(int j=0; j<4; j++){
pair<int,int> nx={x.first+dx[j],x.second+dy[j]};
if(got.find(nx)==got.end()) q.push(nx);
}
}
while(!q.empty()) q.pop();
}
if(can){
cout << "YES\n";
for(int i=0; i<n; i++) cout << arr[i].second+1 << ' ';
return 0;
}
} while(next_permutation(arr+1,arr+n));
assert(false);
cout << "NO";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
344 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
344 KB |
ans=YES N=9 |
| 6 |
Incorrect |
0 ms |
348 KB |
Added cell 5 (0,0) not reachable from infinity |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
344 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
344 KB |
ans=YES N=9 |
| 6 |
Incorrect |
0 ms |
348 KB |
Added cell 5 (0,0) not reachable from infinity |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
344 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
344 KB |
ans=YES N=9 |
| 6 |
Incorrect |
0 ms |
348 KB |
Added cell 5 (0,0) not reachable from infinity |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
344 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
344 KB |
ans=YES N=9 |
| 6 |
Incorrect |
0 ms |
348 KB |
Added cell 5 (0,0) not reachable from infinity |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2648 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
