#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 32768
#define INF 1000000000000000
#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
const int M = 5e5;
bool check[M] = {};
vector<pair<ll,ll>>v;
map<pair<ll,ll>,ll> mp;
vector<int> ans;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
void doo(ll x, ll y)
{
if(mp[{x-1,y}] > 0 && check[mp[{x-1,y}]] == 0)
{
check[mp[{x-1,y}]] = 1;
ans.push_back(mp[{x-1,y}]);
doo(x-1,y);
}
if(mp[{x+1,y}] > 0 && check[mp[{x+1,y}]] == 0)
{
check[mp[{x+1,y}]] = 1;
ans.push_back(mp[{x+1,y}]);
doo(x+1,y);
}
if(mp[{x,y-1}] > 0 && check[mp[{x,y-1}]] == 0)
{
check[mp[{x,y-1}]] = 1;
ans.push_back(mp[{x,y-1}]);
doo(x,y-1);
}
}
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int n, t;
cin >> n >> t;
ll cnt = 1;
for(int i = 0; i < n; i++)
{
ll x, y;
cin >> x >> y;
v.push_back({x,y});
mp[{x,y}] = cnt;
cnt++;
}
sort(v.begin(),v.end());
check[mp[{v[0].first,v[0].second}]] = 1;
ans.push_back(mp[{v[0].first,v[0].second}]);
for(int i = 1; i < n; i++)
{
if(check[mp[{v[i].first,v[i].second}]] == 0)
{
if(mp[ {v[i].first-1,v[i].second}] > 0 && check[mp[ {v[i].first-1,v[i].second}]] == 1)
{
check[mp[ {v[i].first,v[i].second}]] = 1;
ans.push_back(mp[{v[i].first,v[i].second}]);
}
else if(mp[ {v[i].first+1,v[i].second}] > 0 && check[mp[ {v[i].first+1,v[i].second}]] == 1)
{
check[mp[ {v[i].first,v[i].second}]] = 1;
ans.push_back(mp[{v[i].first,v[i].second}]);
}
else if(mp[ {v[i].first,v[i].second-1}] > 0 && check[mp[ {v[i].first,v[i].second-1}]] == 1)
{
check[mp[ {v[i].first,v[i].second}]] = 1;
ans.push_back(mp[{v[i].first,v[i].second}]);
}
}
if(check[mp[{v[i].first,v[i].second}]] = 1)
{
doo(v[i].first,v[i].second);
}
}
bool ok = true;
for(int i = 1; i < n; i++)
{
if(check[i] == 0)
{
ok = false;
break;
}
}
if(ok)
{
cout << "YES" << endl;
for(int i = 0; i < ans.size(); i++)
cout << ans[i] << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:77:48: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
77 | if(check[mp[{v[i].first,v[i].second}]] = 1)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
skyscrapers.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
212 KB |
ans=YES N=4 |
| 3 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
212 KB |
ans=YES N=4 |
| 3 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
212 KB |
ans=YES N=4 |
| 3 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
0 ms |
212 KB |
ans=YES N=4 |
| 3 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
8504 KB |
Full cells must be connected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
