#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);
const int N = (int)1e5 + 100;
int dir[8][2] = {{-1,-1},{0,-1},{+1,-1},{+1,0},{+1,+1},{0,+1},{-1,+1},{-1,0}};
int adj[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};
set<pii> graf;
map<pii, int> full;
map<pii, int> col;
int ci[N], cj[N];
priority_queue<int> cand;
set<pii> vso;
void check(pii cur){
vso.insert(cur);
pii nx;
for(int q =0 ; q < 8 ; q ++ ){
nx = mp(cur.fi+dir[q][0],cur.se+dir[q][1]);
if(!vso.count(nx) && full.count(nx)){
check(nx);
}
}
}
void add_outside(pii cur){
pii nx;
col[cur]=0;
for(int d = 0; d < 4; d ++ ){
nx = mp(cur.fi+adj[d][0],cur.se+adj[d][1]);
if(!graf.count(nx)) continue;
if(full.count(nx)){
cand.push(full[nx]);
}
else{
if(!col.count(nx) || col[nx] > 0){
add_outside(nx);
}
}
}
}
void fillc(pii cur, int cl){
pii nx;
col[cur]=cl;
for(int d = 0; d < 4; d ++ ){
nx = mp(cur.fi+adj[d][0],cur.se+adj[d][1]);
if(!graf.count(nx)) continue;
if(full.count(nx)) continue;
if(col.count(nx)) continue;
fillc(nx,cl);
}
}
bool is_valid(pii xx){
vector<int> q;
pii nx;
int cnt = 0;
for(int t = 0; t < 8 ; t ++ ){
nx = mp(xx.fi + dir[t][0], xx.se + dir[t][1]);
if(full.count(nx)){
cnt ++ ;
q.push_back(-1);
}
else{
q.push_back(col[nx]);
}
}
if(cnt <= 1) return true;
int pt, qt;
for(int t = 0 ; t < 8 ; t += 2){ // corner
pt = (t - 1 + 8) % 8;
qt = (t + 1) % 8;
if(q[t] == -1 && q[pt] >= 0 && q[pt] == q[qt]){
return false;
}
}
if(q[1] >= 0 && q[1] == q[5] && min({q[2],q[3],q[4]}) == -1 && min({q[0],q[6],q[7]}) == -1){
return false;
}
if(q[3] >= 0 && q[3] == q[7] && min({q[0],q[1],q[2]}) == -1 && min({q[4],q[5],q[6]}) == -1){
return false;
}
return true;
}
bool active[N];
int main(){
fastIO;
int n, tip;
cin >> n >> tip;
pii nx;
pii low = mp((int)1e9 + 7, (int)1e9 + 7);
for(int i = 1; i <= n; i ++ ){
cin >> ci[i] >> cj[i];
active[i]=true;
graf.insert(mp(ci[i],cj[i]));
full[mp(ci[i],cj[i])]=i;
for(int j = 0 ;j < 8; j ++ ){
nx = mp(ci[i]+dir[j][0],cj[i]+dir[j][1]);
low = min(low, nx);
graf.insert(nx);
}
}
for(int p = -1; p <= 4; p ++ ){
for(int q = -2; q <= 0 ; q ++ ){
if(full.count(mp(q,p))){
cout << "#";
}
else{
cout << ".";
}
}
cout << "\n";
}
check(mp(ci[1],cj[1]));
if(vso.size() != n){
cout << "NO\n";
return 0;
}
add_outside(low);
int cnt = 1;
for(auto v : graf){
if(full.count(v) || col.count(v)) continue;
fillc(v, cnt);
cnt ++ ;
}
int node;
vector<int> que;
int hi, wi;
for(int delet = 0; delet < n; delet ++ ){
while(!cand.empty()){
node = cand.top();
cand.pop();
if(!active[node]){
continue;
}
if(is_valid(mp(ci[node],cj[node]))){
active[node]=false;
que.push_back(node);
full.erase(mp(ci[node],cj[node]));
for(int t = 0; t < 4; t ++ ){
if(!full.count(mp(ci[node]+adj[t][0],cj[node]+adj[t][1]))){
col[mp(ci[node]+adj[t][0],cj[node]+adj[t][1])]=1;
}
}
add_outside(mp(ci[node],cj[node]));
break;
}
}
}
cout << "YES\n";
reverse(que.begin(), que.end());
for(auto x : que){
cout << x << " ";
}
cout << "\n";
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:130:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
130 | if(vso.size() != n){
| ~~~~~~~~~~~^~~~
skyscrapers.cpp:143:9: warning: unused variable 'hi' [-Wunused-variable]
143 | int hi, wi;
| ^~
skyscrapers.cpp:143:13: warning: unused variable 'wi' [-Wunused-variable]
143 | int hi, wi;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1260 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
17260 KB |
YES or NO expected, but ### found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1260 KB |
YES or NO expected, but ... found |
| 2 |
Halted |
0 ms |
0 KB |
- |
