#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 dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,+1},{+1,+1},{+1,0},{+1,-1},{0,-1}};
int dv[4][2] = {{-1,0},{+1,0},{0,+1},{0,-1}};
const int N = 151169;
const int M = (int)4e6;
pii vv[M];
set<int> Q[M];
int par[M];
map<pii,int> indx;
map<pii,int> emp;
map<pii,int> vis;
int deg[N];
int xi[N], yi[N];
int cnt = 0;
void dfs(pii cur){
cnt ++ ;
vis[cur]=true;
pii go;
for(int p = 0 ; p < 8 ; p ++ ){
go = mp(cur.fi+dir[p][0],cur.se+dir[p][1]);
if(indx.count(go) && !vis[go]){
dfs(go);
}
}
}
pii low = mp((int)1e9 + 7, (int)1e9 + 7);
int fin(int x){
if(par[x]==x) return x;
return par[x]=fin(par[x]);
}
void unite(int u, int v){
u=fin(u);
v=fin(v);
if(u==v) return;
if(Q[u].size() > Q[v].size()) swap(u,v);
for(auto x : Q[u]){
Q[v].insert(x);
}
Q[u].clear();
par[u]=v;
}
bool can_remove(pii yi){
vector<int> c;
pii nx;
for(int d = 0; d < 8 ; d ++ ){
nx = mp(yi.fi + dir[d][0], yi.se + dir[d][1]);
if(!emp.count(nx)) {
c.push_back(-1);
}
else c.push_back(fin(emp[nx]));
}
int cnt = 0;
for(auto x : c) if(x == -1) cnt ++ ; // full cells
if(cnt >= 7 || cnt <= 1) return true;
int p, q;
for(int i = 0 ; i < 8; i += 2 ){
q = (i + 1) % 8;
p = (i - 1 + 8) % 8;
if(c[i] == -1 && c[p] >= 0 && c[p] == c[q]){ // cut off
return false;
}
}
if(c[1] >= 0 && c[1] == c[5] && min({c[0],c[7],c[6]}) == -1 && min({c[2],c[5],c[4]}) == -1){
return false;
}
if(c[7] >= 0 && c[7] == c[3] && min({c[0],c[1],c[2]}) == -1 && min({c[4],c[5],c[6]}) == -1){
return false;
}
return true;
}
int main(){
fastIO;
freopen("in.txt","r",stdin);
int n, typ;
cin >> n >> typ;
for(int i = 1; i <= n; i ++ ){
cin >> xi[i] >> yi[i];
indx[mp(xi[i],yi[i])]=i;
}
pii nx;
int id=0;
for(int i = 1;i <= n; i ++ ){
for(int d = 0; d < 8 ; d ++ ){
nx = mp(xi[i]+dir[d][0],yi[i]+dir[d][1]);
if(indx.count(nx)){
deg[i]++;
continue;
}
if(!emp.count(nx)){
emp[nx]=id;
vv[id]=nx;
par[id]=id;
id++;
}
Q[emp[nx]].insert(i);
}
}
for(int i = 0 ; i < id; i ++ ){
low = min(low, vv[i]);
for(int j = 0 ; j < 4; j ++ ){
nx = mp(vv[i].fi+dv[j][0], vv[i].se+dv[j][1]);
if(emp.count(nx)){
unite(i,emp[nx]);
}
}
}
dfs(mp(xi[1],yi[1]));
if(cnt != n){
cout << "NO\n";
return 0;
}
vector<int> ord;
int cid;
cout << "YES\n";
set<int> bad;
int idx;
for(int i = 0 ; i < n; i ++ ){
cid = fin(emp[low]);
while(!Q[cid].empty()){
auto it = Q[cid].end();
-- it;
if(can_remove(mp(xi[*it],yi[*it]))){
idx = *it;
ord.push_back(idx);
Q[cid].erase(it);
indx[mp(xi[idx],yi[idx])]=0;
par[id]=id;
vv[id]=mp(xi[idx],yi[idx]);
emp[mp(xi[idx],yi[idx])]=id;
for(int d = 0 ; d < 8 ; d ++ ){
nx = mp(xi[idx]+dir[d][0], yi[idx]+dir[d][1]);
if(indx[nx]>0){
deg[indx[nx]]--;
if(deg[indx[nx]] <= 1 && bad.count(indx[nx])){
bad.erase(indx[nx]);
Q[cid].insert(indx[nx]);
}
}
else{
Q[fin(emp[nx])].erase(idx);
}
}
for(int d = 0; d < 4 ; d ++ ){
nx = mp(xi[idx]+dir[d][0],yi[idx]+dir[d][1]);
if(emp.count(nx)){
unite(id,emp[nx]);
}
}
id ++ ;
break;
}
else{
bad.insert(*it);
Q[cid].erase(it);
}
}
cid = fin(emp[low]);
}
reverse(ord.begin(),ord.end());
for(auto yy : ord){
cout << yy << "\n";
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
92 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
188268 KB |
Contestant did not find solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
188268 KB |
Contestant did not find solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
188268 KB |
Contestant did not find solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
188268 KB |
ans=NO N=1934 |
| 2 |
Correct |
126 ms |
188268 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
130 ms |
188396 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
188268 KB |
Contestant did not find solution |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
188268 KB |
ans=NO N=66151 |
| 2 |
Correct |
130 ms |
188480 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
132 ms |
188268 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
188268 KB |
ans=NO N=1934 |
| 2 |
Correct |
126 ms |
188268 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
130 ms |
188396 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
