bool home = 0;
#include <bits/stdc++.h>
using namespace std;
struct T
{
int x;
int y;
};
bool operator < (T a, T b)
{
if (a.x != b.x)
{
return a.x < b.x;
}
return a.y < b.y;
}
const int N = 150000 + 7;
int n;
int task;
T points[N];
map<T, int> w;
bool vis[N];
int dirx[] = {-1, 0, 1, 0};
int diry[] = {0, 1, 0, -1};
int solution[N];
bool ales_deja[N];
bool sanity_check()
{
int who = -1, cnt = 0;
for (int i = 1; i <= n; i++)
{
vis[i] = 0;
if (ales_deja[i])
{
continue;
}
who = i;
cnt++;
}
if (cnt == 0)
{
return 1;
}
vector<int> q = {who};
vis[who] = 1;
for (int i = 0; i < (int) q.size(); i++)
{
int a = q[i];
for (int dx = -1; dx <= +1; dx++)
{
for (int dy = -1; dy <= +1; dy++)
{
T nw = {points[a].x + dx, points[a].y + dy};
if (w.count(nw))
{
int b = w[nw];
if (ales_deja[b])
{
continue;
}
if (vis[b] == 0)
{
vis[b] = 1;
q.push_back(b);
}
}
}
}
}
if ((int) q.size() < cnt)
{
return 0;
}
assert((int) q.size() == cnt);
return 1;
}
int main()
{
if (home == 0)
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
else
{
freopen ("input.txt", "r", stdin);
}
cin >> n >> task;
assert(task == 1 || task == 2);
for (int i = 1; i <= n; i++)
{
cin >> points[i].x >> points[i].y;
w[points[i]] = i;
}
{
/// Just run a quick BFS to check whether or not the answer is NO
if (!sanity_check())
{
cout << "NO\n";
return 0;
}
}
map<T, int> ids;
vector<int> t;
vector<int> ext_tag;
function<int(int)> get_inner_root = [&] (int a)
{
if (t[a] == a)
{
return a;
}
else
{
return t[a] = get_inner_root(t[a]);
}
};
function<int(T)> get_root = [&] (T a)
{
if (!ids.count(a))
{
ids[a] = (int) t.size();
t.push_back((int) t.size());
ext_tag.push_back(0);
}
return get_inner_root(ids[a]);
};
function<void(T, T)> join = [&] (T x, T y)
{
int a = get_root(x);
int b = get_root(y);
if (a == b)
{
return;
}
t[a] = b;
ext_tag[b] |= ext_tag[a];
};
for (int i = 1; i <= n; i++)
{
for (int dx = -1; dx <= +1; dx++)
{
for (int dy = -1; dy <= +1; dy++)
{
T nw = {points[i].x + dx, points[i].y + dy};
if (!w.count(nw))
{
int gunoi = get_root(nw);
}
}
}
}
assert(!ids.empty());
ext_tag[get_root(ids.begin()->first)] = 1;
for (auto &iter : ids)
{
T guy = iter.first;
for (int k = 0; k < 4; k++)
{
int dx = dirx[k];
int dy = diry[k];
T nw = {guy.x + dx, guy.y + dy};
if (ids.count(nw))
{
join(guy, nw);
}
}
}
for (auto &iter : ids)
{
T guy = iter.first;
}
cout << "YES\n";
/*for (auto &it : ids)
{
cout << it.first.x << " " << it.first.y << " " << "P" << it.second << "\n";
}*/
for (int step = n; step >= 1; step--)
{
for (int i = n; i >= 1; i--)
{
if (ales_deja[i])
{
continue;
}
bool has_access = 0;
for (int k = 0; k < 4; k++)
{
int dx = dirx[k];
int dy = diry[k];
T nw = {points[i].x + dx, points[i].y + dy};
if (w.count(nw))
{
int j = w[nw];
if (ales_deja[j] == 0)
{
continue;
}
}
///cout << " > " << nw.x << " " << nw.y << "\n";
assert(ids.count(nw));
has_access |= (ext_tag[get_root(nw)]);
}
if (has_access)
{
ales_deja[i] = 1;
if (sanity_check() == 0)
{
ales_deja[i] = 0;
continue;
}
int gunoi = get_root(points[i]);
solution[step] = i;
break;
}
}
assert(solution[step] != -1);
}
for (int i = 1; i <= n; i++)
{
cout << solution[i] << "\n";
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:164:15: warning: unused variable 'gunoi' [-Wunused-variable]
164 | int gunoi = get_root(nw);
| ^~~~~
skyscrapers.cpp:190:7: warning: variable 'guy' set but not used [-Wunused-but-set-variable]
190 | T guy = iter.first;
| ^~~
skyscrapers.cpp:235:13: warning: unused variable 'gunoi' [-Wunused-variable]
235 | int gunoi = get_root(points[i]);
| ^~~~~
skyscrapers.cpp:91:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen ("input.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
Correct |
1 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Incorrect |
0 ms |
212 KB |
Integer 0 violates the range [1, 9] |
| 6 |
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 |
Correct |
1 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Incorrect |
0 ms |
212 KB |
Integer 0 violates the range [1, 9] |
| 6 |
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 |
Correct |
1 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Incorrect |
0 ms |
212 KB |
Integer 0 violates the range [1, 9] |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
468 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
2241 ms |
496 KB |
Integer 0 violates the range [1, 1824] |
| 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 |
Correct |
1 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 5 |
Incorrect |
0 ms |
212 KB |
Integer 0 violates the range [1, 9] |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
5620 KB |
ans=NO N=66151 |
| 2 |
Correct |
26 ms |
4836 KB |
ans=NO N=64333 |
| 3 |
Execution timed out |
3592 ms |
6616 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
468 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
2241 ms |
496 KB |
Integer 0 violates the range [1, 1824] |
| 4 |
Halted |
0 ms |
0 KB |
- |
