/* be name khoda */
// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;
#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif
typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;
#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))
#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl
const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;
#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD
// -----------------------------------------------------------------------
const ll maxn = 100010;
const ll maxv = 5000000;
ll n, vn, V[maxn][2], H[maxn][2], Vi[maxn][2], Hi[maxn][2], seg[maxn * 4];
ll scc[maxv], sccn, st[maxv], sn, stk[maxv], up[maxv];
pii P[maxn];
vi out[maxv];
bool fst[maxn], instk[maxv], val[maxv];
inline ll VL(ll x) {
return x << 1;
}
inline ll HL(ll y) {
return y << 1 ^ 1;
}
void halt() {
cout << "NE\n";
exit(0);
}
void add_edge(ll a, ll b) {
out[a].pb(b);
out[b ^ 1].pb(a ^ 1);
}
void process_points() {
fori (i, n) {
auto [x, y] = P[i];
if (!V[x][1] && !H[y][1]) halt();
else if (V[x][1] && !H[y][1]) {
add_edge(VL(x) << 1 ^ 1, VL(x) << 1);
} else if (!V[x][1] && H[y][1]) {
add_edge(HL(y) << 1 ^ 1, HL(y) << 1);
} else {
add_edge(VL(x) << 1 ^ 1, HL(y) << 1);
add_edge(VL(x) << 1, HL(y) << 1 ^ 1);
}
}
}
void build(ll x = 1, ll l = 0, ll r = maxn) {
seg[x] = vn++;
if (r - l > 1) {
build(XL, l, MD);
build(XR, MD, r);
add_edge(seg[x] << 1 ^ 1, seg[XL] << 1 ^ 1);
add_edge(seg[x] << 1 ^ 1, seg[XR] << 1 ^ 1);
}
}
void conn_lr(ll li, ll ri, ll v, ll x = 1, ll l = 0, ll r = maxn) {
if (li >= r || l >= ri) {
} else if (li <= l && r <= ri) {
add_edge(v << 1, seg[x] << 1 ^ 1);
} else {
conn_lr(li, ri, v, XL, l, MD);
conn_lr(li, ri, v, XR, MD, r);
}
}
void change(ll p, ll v, ll x = 1, ll l = 0, ll r = maxn) {
if (r - l == 1) {
seg[x] = v;
} else {
if (p < MD) {
change(p, v, XL, l, MD);
} else {
change(p, v, XR, MD, r);
}
seg[x] = vn++;
add_edge(seg[x] << 1 ^ 1, seg[XL] << 1 ^ 1);
add_edge(seg[x] << 1 ^ 1, seg[XR] << 1 ^ 1);
}
}
void sweepline() {
vn = maxn * 2;
build();
fori (y, maxn) {
if (H[y][1]) conn_lr(H[y][0] + 1, H[y][1], HL(y));
fori (i, 2) if (H[y][i]) {
ll x = H[y][i];
if (!fst[x]) {
change(x, VL(x));
} else {
++vn;
change(x, vn - 1);
}
fst[x] ^= 1;
}
}
}
ll stt;
void dfs(ll x) {
st[x] = up[x] = stt++;
instk[x] = 1;
stk[sn++] = x;
for (auto y : out[x]) {
if (!st[y]) {
dfs(y);
smin(up[x], up[y]);
} else if (instk[y]) {
smin(up[x], st[y]);
}
}
if (st[x] == up[x]) {
ll y;
do {
y = stk[--sn];
scc[y] = sccn;
instk[y] = 0;
} while (y != x);
++sccn;
}
}
void two_sat() {
stt = 1;
fori (i, vn << 1) {
if (!st[i]) dfs(i);
}
fori (i, vn) {
if (scc[i << 1] == scc[i << 1 ^ 1]) halt();
val[i] = scc[i << 1] < scc[i << 1 ^ 1];
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
fori (i, n) {
ll x, y; cin >> x >> y;
P[i] = {x, y};
if (V[x][0] == 0) V[x][0] = y, Vi[x][0] = i;
else {
V[x][1] = y, Vi[x][1] = i;
if (V[x][0] > V[x][1]) swap(V[x][0], V[x][1]), swap(Vi[x][0], Vi[x][1]);
}
if (H[y][0] == 0) H[y][0] = x, Hi[y][0] = i;
else {
H[y][1] = x, Hi[y][1] = i;
if (H[y][0] > H[y][1]) swap(H[y][0], H[y][1]), swap(Hi[y][0], Hi[y][1]);
}
}
process_points();
sweepline();
two_sat();
cout << "DA\n";
fori (i, maxn) {
if (val[VL(i)] && V[i][1]) cout << Vi[i][0] + 1 << ' ' << Vi[i][1] + 1 << '\n';
if (val[HL(i)] && H[i][1]) cout << Hi[i][0] + 1 << ' ' << Hi[i][1] + 1 << '\n';
}
debug(vn << 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
139128 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
139128 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
139128 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
139128 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
139128 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
