#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
using lll = __int128;
using ll = long long;
using ld = long double;
const int N = 2e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;
int n;
vii a;
vii A;
struct dsu
{
int fat[N];
int combo = 0;
dsu()
{
iota(fat, fat + N, 0);
}
int find(int x) { return fat[x] = (fat[x] == x ? x : find(fat[x])); }
void link(int u, int v)
{
u = find(u);
v = find(v);
if (u != v)
fat[u] = v, combo--;
}
} de;
bool chk()
{
de.combo = n;
map<pair<int, int>, int> rak;
for (int i = 0; i < n; ++i)
rak[A[i]] = i + 1;
for (auto u : A)
{
inc(j, -1, 1) inc(k, -1, 1)
{
pii c = {u.f + j, u.s + k};
if (rak[c])
{
de.link(rak[c], rak[u]);
}
}
}
return de.combo == 1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n;
int t;
cin >> t;
map<int, vi> mp;
for (int i = 0; i < n; ++i)
{
int x, y;
cin >> x >> y;
mp[x + y].pb(i);
// a.pb({x + y, i + 1});
A.pb({x, y});
}
map<pii, bool> hasm;
auto hasn = [&](int x, int y) -> bool {
inc(j, -1, 1) inc(k, -1, 1)
{
pii c = {x + j, y + k};
if (hasm[c])
{
return 1;
}
}
return 0;
};
if (chk())
{
vi ans;
{ // t = 1
int cnt = 0;
for (auto it : mp)
{
set<int> st;
for (auto u : it.s)
st.insert(u);
while (sz(st))
{
bool ok = 0;
for (auto u : st)
{
if (hasn(A[u].f, A[u].s) || cnt == 0)
{
hasm[{A[u].f, A[u].s}] = 1;
ans.pb(u);
st.erase(u);
ok = 1;
break;
}
}
if (!ok)
{
return cout << "NO", 0;
}
}
cnt++;
}
}
cout << "YES\n";
for (auto u : ans)
cout << ++u << "\n";
}
else
{
cout << "NO";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1132 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
1132 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
1132 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
1132 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 7 |
Correct |
1 ms |
1132 KB |
ans=NO N=9 |
| 8 |
Correct |
1 ms |
1132 KB |
ans=NO N=10 |
| 9 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 10 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 11 |
Incorrect |
1 ms |
1132 KB |
Full cells must be connected |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1132 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
1132 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
1132 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
1132 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 7 |
Correct |
1 ms |
1132 KB |
ans=NO N=9 |
| 8 |
Correct |
1 ms |
1132 KB |
ans=NO N=10 |
| 9 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 10 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 11 |
Incorrect |
1 ms |
1132 KB |
Full cells must be connected |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1132 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
1132 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
1132 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
1132 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 7 |
Correct |
1 ms |
1132 KB |
ans=NO N=9 |
| 8 |
Correct |
1 ms |
1132 KB |
ans=NO N=10 |
| 9 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 10 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 11 |
Incorrect |
1 ms |
1132 KB |
Full cells must be connected |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2412 KB |
ans=NO N=1934 |
| 2 |
Correct |
6 ms |
1644 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
6 ms |
1260 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1132 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
1132 KB |
ans=YES N=4 |
| 3 |
Correct |
1 ms |
1132 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 5 |
Correct |
1 ms |
1132 KB |
ans=YES N=9 |
| 6 |
Correct |
1 ms |
1132 KB |
ans=YES N=5 |
| 7 |
Correct |
1 ms |
1132 KB |
ans=NO N=9 |
| 8 |
Correct |
1 ms |
1132 KB |
ans=NO N=10 |
| 9 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 10 |
Correct |
1 ms |
1132 KB |
ans=YES N=10 |
| 11 |
Incorrect |
1 ms |
1132 KB |
Full cells must be connected |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
367 ms |
8672 KB |
ans=NO N=66151 |
| 2 |
Correct |
394 ms |
30588 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
365 ms |
6624 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2412 KB |
ans=NO N=1934 |
| 2 |
Correct |
6 ms |
1644 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
6 ms |
1260 KB |
Contestant did not find solution |
| 4 |
Halted |
0 ms |
0 KB |
- |
