#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int d4[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};
int d8[8][2] = {{-1,-1},{0,-1},{+1,-1},{+1,0},{+1,+1},{0,+1},{-1,-1},{-1,0}};
const int N = 150101;
const int M = N * 9;
set<int> Q[M];
map<pii,int> idx;
map<pii,int> emp;
map<pii,int> out;
int ii[N], jj[N];
pii vv[M];
int par[M];
int id;
bool active[M];
int fin(int x){
if(x==par[x]) return x;
return par[x]=fin(par[x]);
}
void unite(int p, int q){
// an element can be added at most 8? times therefore it is optimal
p=fin(p);
q=fin(q);
if(p==q) return;
if(Q[p].size() > Q[q].size()) swap(p,q);
par[p]=q;
for(auto x : Q[p]){
Q[q].insert(x);
}
Q[p].clear();
}
bool has[N];
void check(int id){
has[id]=true;
pii go;
for(int t = 0 ; t < 8 ; t ++ ){
go = mp(ii[id]+d8[t][0],jj[id]+d8[t][1]);
if(idx.count(go)){
if(!has[idx[go]]){
check(idx[go]);
}
}
}
}
bool can_kill(pii vv){
vector<int> q;
pii nx;
int cnt = 0;
for(int i = 0 ; i < 8 ; i ++ ){
nx = mp(vv.fi + d8[i][0], vv.se + d8[i][1]);
if(emp.count(nx)){
q.push_back(fin(emp[nx]));
}
else{
cnt ++ ;
q.push_back(-1);
}
}
if(cnt <= 1 || cnt >= 7) return true;
int pv, qv;
for(int d = 0; d < 8; d += 2){ // corners
pv = (d + 8 - 1) % 8;
qv = (d + 1) % 8;
if(q[d] == -1 && q[pv] >= 0 && q[pv] == q[qv]){
return false;
}
}
// side cut
if(q[1] == q[5] && q[1] >= 0 && min({q[0],q[6],q[7]}) == -1 && min({q[2],q[3],q[4]}) == -1){
return false;
}
if(q[3] == q[6] && q[3] >= 0 && min({q[0],q[1],q[2]}) == -1 && min({q[4],q[5],q[6]}) == -1){
return false;
}
return true;
}
int main(){
fastIO;
int n;
cin >> n;
int typ;
cin >> typ;
for(int i = 1; i <= n; i ++) {
cin >> ii[i] >> jj[i];
idx[mp(ii[i],jj[i])] = i;
active[i]=true;
}
pii nx;
pii low = mp((int)1e9+7,(int)1e9+7);
for(int i = 1; i <= n; i ++ ){
for(int q = 0; q < 8; q ++ ){
nx = mp(ii[i] + d8[q][0], jj[i] + d8[q][1]);
if(idx.count(nx)) continue;
if(!emp.count(nx)){
emp[nx]=id;
vv[id]=nx;
par[id]=id;
id++;
}
Q[emp[nx]].insert(i);
low = min(low, nx);
}
}
for(int i = 0 ; i < id; i ++ ){
for(int j = 0 ; j < 4; j ++) {
nx = mp(vv[i].fi+d4[j][0], vv[i].se+d4[j][1]);
if(emp.count(nx)){
unite(i,emp[nx]);
}
}
}
for(auto x : Q[fin(emp[low])]){
out[mp(ii[x],jj[x])]=true;
}
check(1);
for(int i = 1; i <= n; i ++ ){
if(!has[i]){
cout << "NO\n";
return 0;
}
}
vector<int> soln;
int cid;
int chk;
int nah;
for(int delet = 0 ; delet < n; delet ++ ){
cid = fin(emp[low]);
while(!Q[cid].empty()){
auto it = Q[cid].end();
-- it;
chk = *it;
Q[cid].erase(it);
if(!active[chk]){
continue;
}
if(can_kill(mp(ii[chk],jj[chk]))){
active[chk]=false;
soln.push_back(chk);
idx[mp(ii[chk],jj[chk])]=0;
emp[mp(ii[chk],jj[chk])]=id;
par[id]=id;
for(int d = 0; d < 4; d ++ ){
nx = mp(ii[chk]+d4[d][0],jj[chk]+d4[d][1]);
if(idx.count(nx) && idx[nx]>0){
out[nx]=true;
Q[id].insert(idx[nx]);
}
}
for(int d = 0 ;d < 4; d ++ ){
nx = mp(ii[chk]+d4[d][0],jj[chk]+d4[d][1]);
if(emp.count(nx)){
nah = emp[nx];
unite(id,nah);
}
}
for(int d = 0; d < 8 ; d ++ ){
nx = mp(ii[chk]+d8[d][0],jj[chk]+d8[d][1]);
if(idx[nx] > 0 && out.count(nx)){
Q[fin(id)].insert(idx[nx]);
}
}
id++;
break;
}
}
}
reverse(soln.begin(), soln.end());
cout << "YES\n";
for(auto x : soln)
cout << x << " ";
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
63852 KB |
ans=YES N=1 |
| 2 |
Correct |
43 ms |
63852 KB |
ans=YES N=4 |
| 3 |
Correct |
43 ms |
63852 KB |
ans=NO N=4 |
| 4 |
Incorrect |
44 ms |
63852 KB |
Contestant did not find solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
63852 KB |
ans=YES N=1 |
| 2 |
Correct |
43 ms |
63852 KB |
ans=YES N=4 |
| 3 |
Correct |
43 ms |
63852 KB |
ans=NO N=4 |
| 4 |
Incorrect |
44 ms |
63852 KB |
Contestant did not find solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
63852 KB |
ans=YES N=1 |
| 2 |
Correct |
43 ms |
63852 KB |
ans=YES N=4 |
| 3 |
Correct |
43 ms |
63852 KB |
ans=NO N=4 |
| 4 |
Incorrect |
44 ms |
63852 KB |
Contestant did not find solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
65644 KB |
ans=NO N=1934 |
| 2 |
Correct |
54 ms |
64620 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
50 ms |
64256 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
63852 KB |
ans=YES N=1 |
| 2 |
Correct |
43 ms |
63852 KB |
ans=YES N=4 |
| 3 |
Correct |
43 ms |
63852 KB |
ans=NO N=4 |
| 4 |
Incorrect |
44 ms |
63852 KB |
Contestant did not find solution |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
676 ms |
84016 KB |
ans=NO N=66151 |
| 2 |
Correct |
1378 ms |
114284 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
366 ms |
76780 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
65644 KB |
ans=NO N=1934 |
| 2 |
Correct |
54 ms |
64620 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
50 ms |
64256 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
