#include<bits/stdc++.h>
using namespace std;
//Types
using ll = long long;
using db = double;
//Vectors
#define pb push_back
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(), vec.end()
//things
#define f first
#define s second
const int SMALLINF = 1e9 + 7;
const ll BIGINF = ((ll)1e18) + 7;
#define Speeed ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);
ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
// struct info{
//
// ll x, y, pos;
// };
void solve(){
ll n, t;
cin>>n>>t;
vector<pair<ll, ll> > vec(n);
vector<pair<ll, pair<ll, ll> > > ex(n);
map<pair<ll, ll>, bool> visited, exist;
map<pair<ll, ll>, ll> order;
for(ll i = 0; i < n; i++){
cin>>ex[i].s.f>>ex[i].s.s;
ex[i].f = i+1;
}
sort(all(ex));
for(ll i = 0; i < n; i++){
vec[i].f = ex[i].s.f;
vec[i].s = ex[i].s.s;
pair<ll, ll> p;
p.f = vec[i].f;
p.s = vec[i].s;
exist[p] = true;
order[p] = i+1;
}
sort(all(vec));
visited[vec[0]] = true;
priority_queue<pair<ll, pair<ll, ll> >, vector<pair<ll, pair<ll, ll> > >, greater<pair<ll, pair<ll, ll> > > > pq;
pq.push({order[vec[0]], vec[0]});
vector<ll> res;
while(sz(pq)){
ll x = pq.top().s.f, y = pq.top().s.s, pos = pq.top().f;
pq.pop();
for(ll i = 0; i < 8; i++){
pair<ll, ll> pch;
pch.f = x+dx[i], pch.s = y+dy[i];
if(exist[pch] and !visited[pch]){
visited[pch] = true;
pair<ll, pair<ll, ll>> qq;
qq.s.f = pch.f;
qq.s.s = pch.s;
qq.f = order[pch];
pq.push(qq);
}
}
res.pb(pos);
}
if(sz(res)==n){
cout<<"YES\n";
for(ll i = 0; i < sz(res); i++){
cout<<res[i]<<" ";
}
}
else cout<<"NO\n";
}
int main(){
Speeed
ll t=1;
// cin>>t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
ans=NO N=1934 |
| 2 |
Correct |
2 ms |
596 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
5 ms |
724 KB |
Added cell 1824 (370,234) not reachable from infinity |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
305 ms |
19144 KB |
ans=NO N=66151 |
| 2 |
Correct |
78 ms |
10824 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
336 ms |
18500 KB |
Added cell 69316 (-22,-94) not reachable from infinity |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
ans=NO N=1934 |
| 2 |
Correct |
2 ms |
596 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
5 ms |
724 KB |
Added cell 1824 (370,234) not reachable from infinity |
| 4 |
Halted |
0 ms |
0 KB |
- |
