#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int MAXN = 1e5 + 5;
const int offset = 1 << 17;
class TwoSat {
int n;
vector <int> sol;
vector <bool> bio;
vector <int> comp;
vector <vector <int>> adj, rev;
stack <int> order;
public:
int add_variables(int vars) {
n += vars;
for (int i = 0; i < 2 * vars; i++) {
sol.push_back(0);
bio.push_back(false);
comp.push_back(0);
adj.push_back(vector <int> ());
rev.push_back(vector <int> ());
}
return n - vars;
}
TwoSat(int _n) {
n = 0;
add_variables(_n);
}
TwoSat(){}
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 set_variable(int u, bool val) {
add_implication(u, val, u, !val);
}
void at_most_one(const vector <pii> &v) {
int sz = v.size();
add_variables(sz);
for (int i = 0; i < sz; i++) {
add_implication(v[i].first, v[i].second, n - i - 1, 0);
if (i) {
add_implication(n - i, 0, n - i - 1, 0);
add_implication(n - i, 0, v[i].first, !v[i].second);
}
}
}
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 solve() {
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 get(int u, int neg) {
return sol[2 * u + neg];
}
};
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> adj[MAXN];
TwoSat Segments;
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);
}
void add_clause(int x, int u, int v) {
Segments.add_implication(u < off[x] ? st[x] + u : tour[x][u - off[x]].second, 0, st[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] = Segments.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) {
return lower_bound(tour[x].begin(), tour[x].end(), pii(val, 0)) - tour[x].begin();
}
void update(int node, int x, int lo, int hi, int from, int to, int var) {
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
Segments.add_implication(st[node] + x, 0, var, 1);
return;
}
int mid = (lo + hi) / 2;
update(node, 2 * x, lo, mid, from, to, var);
update(node, 2 * x + 1, mid, hi, from, to, var);
}
void add_intersections(int x, int down, int up, int var) {
for (x += offset; x; x /= 2)
if (off[x])
update(x, 1, 0, off[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 = Segments.add_variables(1);
segs[tmp] = {hor[i][0], hor[i][1]};
int l = MAXN, r = 0;
for (auto it : hor[i]) {
adj[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 = Segments.add_variables(1);
segs[tmp] = {ver[i][0], ver[i][1]};
int l = MAXN, r = 0;
for (auto it : ver[i]) {
adj[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 (!adj[i].empty())
Segments.add_implication(adj[i][0], 1, adj[i][1 % adj[i].size()], 0);
else
bye();
if (!Segments.solve())
bye();
puts("DA");
for (auto it : segs)
if (Segments.get(it.first, 0))
printf("%d %d\n", it.second.first + 1, it.second.second + 1);
}
int main() {
load();
solve();
return 0;
}
Compilation message
matching.cpp: In function 'void init(int)':
matching.cpp:127: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:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
matching.cpp:100: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 |
Incorrect |
14 ms |
13824 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13824 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13824 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13824 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
13824 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
