#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};
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;
}
sort(arr,arr+n);
do{
bool can=true;
unordered_set<pair<int,int>,custom_hash> got;
for(int i=0; i<n-1; 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)>5) 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,arr+n));
cout << "NO";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
348 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
348 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 7 |
Correct |
1874 ms |
348 KB |
ans=NO N=9 |
| 8 |
Execution timed out |
3547 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
348 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
348 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 7 |
Correct |
1874 ms |
348 KB |
ans=NO N=9 |
| 8 |
Execution timed out |
3547 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
348 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
348 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 7 |
Correct |
1874 ms |
348 KB |
ans=NO N=9 |
| 8 |
Execution timed out |
3547 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3517 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
348 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
348 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
348 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
348 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
348 KB |
ans=YES N=5 |
| 7 |
Correct |
1874 ms |
348 KB |
ans=NO N=9 |
| 8 |
Execution timed out |
3547 ms |
600 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3596 ms |
1112 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3517 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
