#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int MAXN = 1e5 + 5;
const int offset = 1 << 17;
const int MAXV = 1.15e7 + 5;
int n;
bool sol[MAXV];
bool bio[MAXV];
int comp[MAXV];
vector <int> adj[MAXV], rev[MAXV];
stack <int> order;
inline int add_variables(int vars) {
n += vars;
return n - vars;
}
void add_edge(int u, int v) {
adj[u].push_back(v);
rev[v].push_back(u);
}
void add_implication(int u1, int neg1, int u2, int neg2) {
add_edge(2 * u1 + neg1, 2 * u2 + neg2);
add_edge(2 * u2 + !neg2, 2 * u1 + !neg1);
}
void dfs_forward(int x) {
bio[x] = true;
for (auto it : adj[x])
if (!bio[it])
dfs_forward(it);
order.push(x);
}
void dfs_backward(int x, int c) {
comp[x] = c;
for (auto it : rev[x])
if (!comp[it])
dfs_backward(it, c);
}
bool two_sat() {
for (int i = 0; i < 2 * n; i++)
if (!bio[i])
dfs_forward(i);
int ptr = 0;
for (; !order.empty(); order.pop())
if (!comp[order.top()])
dfs_backward(order.top(), ++ptr);
for (int i = 0; i < 2 * n; i++) {
if (comp[i] == comp[i ^ 1])
return false;
sol[i] = comp[i] > comp[i ^ 1];
}
return true;
}
int N;
int x[MAXN], y[MAXN];
vector <pii> tour[2 * offset];
int st[2 * offset], off[2 * offset];
vector <int> hor[MAXN], ver[MAXN];
unordered_map <int, pii> segs;
vector <int> graph[MAXN];
void load() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d%d", x + i, y + i);
hor[y[i]].push_back(i);
ver[x[i]].push_back(i);
}
}
void insert(int x, int lo, int hi, int from, int to, int var, int height) {
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
tour[x].push_back({height, var});
return;
}
int mid = (lo + hi) / 2;
insert(2 * x, lo, mid, from, to, var, height);
insert(2 * x + 1, mid, hi, from, to, var, height);
}
inline int get_id(int node, int x) {
return x < off[node] ? st[node] + x : tour[node][x - off[node]].second;
}
void add_clause(int x, int u, int v) {
if (u < off[x] + tour[x].size())
add_implication(get_id(x, u), 0, get_id(x, v), 0);
}
void init(int x) {
if (tour[x].empty())
return;
off[x] = 1;
sort(tour[x].begin(), tour[x].end());
while (off[x] < tour[x].size())
off[x] *= 2;
st[x] = add_variables(2 * off[x]);
for (int i = 0; i < off[x]; i++) {
add_clause(x, 2 * i, i);
add_clause(x, 2 * i + 1, i);
}
}
int get_bounds(int x, int val) {
int lo = 0, hi = tour[x].size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tour[x][mid].first >= val)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
void update(int node, int from, int to, int var) {
from += off[node];
to += off[node];
while (from < to) {
if (from % 2)
add_implication(get_id(node, from++), 0, var, 1);
if (to % 2)
add_implication(get_id(node, --to), 0, var, 1);
from /= 2;
to /= 2;
}
}
void add_intersections(int x, int down, int up, int var) {
for (x += offset; x; x /= 2)
if (off[x])
update(x, get_bounds(x, down), get_bounds(x, up + 1), var);
}
void bye() {
puts("NE");
exit(0);
}
void solve() {
for (int i = 1; i < MAXN; i++)
if (hor[i].size() == 2) {
int tmp = add_variables(1);
segs[tmp] = {hor[i][0], hor[i][1]};
int l = MAXN, r = 0;
for (auto it : hor[i]) {
graph[it].push_back(tmp);
l = min(l, x[it]);
r = max(r, x[it]);
}
insert(1, 0, offset, l, r + 1, tmp, i);
}
for (int i = 0; i < 2 * offset; i++)
init(i);
for (int i = 1; i < MAXN; i++)
if (ver[i].size() == 2) {
int tmp = add_variables(1);
segs[tmp] = {ver[i][0], ver[i][1]};
int l = MAXN, r = 0;
for (auto it : ver[i]) {
graph[it].push_back(tmp);
l = min(l, y[it]);
r = max(r, y[it]);
}
add_intersections(i, l, r, tmp);
}
for (int i = 0; i < N; i++)
if (!graph[i].empty())
add_implication(graph[i][0], 1, graph[i][1 % graph[i].size()], 0);
else
bye();
if (!two_sat())
bye();
puts("DA");
for (auto it : segs)
if (sol[2 * it.first])
printf("%d %d\n", it.second.first + 1, it.second.second + 1);
}
int main() {
double timer = clock();
load();
solve();
fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
return 0;
}
Compilation message
matching.cpp: In function 'void add_clause(int, int, int)':
matching.cpp:97:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (u < off[x] + tour[x].size())
~~^~~~~~~~~~~~~~~~~~~~~~~~~
matching.cpp: In function 'void init(int)':
matching.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (off[x] < tour[x].size())
~~~~~~~^~~~~~~~~~~~~~~~
matching.cpp: In function 'void load()':
matching.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
matching.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", x + i, y + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
