#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <cassert>
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
const int INF = 10000000;
struct minseg {
int s, e, m;
ii v;
minseg *l, *r;
minseg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2;
v = ii(INF, -1);
l = r = NULL;
}
void update(int i, ii nv) {
if (s != e) {
if (i > m) {
if (r == NULL) r = new minseg(m + 1, e);
r -> update(i, nv);
} else {
if (l == NULL) l = new minseg(s, m);
l -> update(i, nv);
}
v = min(l == NULL ? ii(INF, -1) : l -> v, r == NULL ? ii(INF, -1) : r -> v);
} else v = nv;
}
ii query(int a, int b) {
if (s == a && e == b) return v;
if (a > m) return r == NULL ? ii(INF, -1) : r -> query(a, b);
if (b <= m) return l == NULL ? ii(INF, -1) : l -> query(a, b);
return min(l == NULL ? ii(INF, -1) : l -> query(a, m), r == NULL ? ii(INF, -1) : r -> query(m + 1, b));
}
};
struct minseg2d {
int s, e, m;
minseg *v;
minseg2d *l, *r;
minseg2d(int rs, int re, int cs, int ce) {
s = rs, e = re, m = (s + e) / 2;
v = new minseg(cs, ce);
l = r = NULL;
}
void update(int R, int C, ii nv) {
if (s != e) {
if (R > m) {
if (r == NULL) r = new minseg2d(m + 1, e, v -> s, v -> e);
r -> update(R, C, nv);
} else {
if (l == NULL) l = new minseg2d(s, m, v -> s, v -> e);
l -> update(R, C, nv);
}
v -> update(C, min(l == NULL ? ii(INF, -1) : l -> v -> query(C, C), r == NULL ? ii(INF, -1) : r -> v -> query(C, C)));
} else v -> update(C, nv);
}
ii query(int rs, int re, int cs, int ce) {
if (s == rs && e == re) return v -> query(cs, ce);
if (rs > m) return r == NULL ? ii(INF, -1) : r -> query(rs, re, cs, ce);
if (re <= m) return l == NULL ? ii(INF, -1) : l -> query(rs, re, cs, ce);
return min(l == NULL ? ii(INF, -1) : l -> query(rs, m, cs, ce), r == NULL ? ii(INF, -1) : r -> query(m + 1, re, cs, ce));
}
};
struct maxseg {
int s, e, m;
ii v;
maxseg *l, *r;
maxseg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2;
v = ii(0, -1);
l = r = NULL;
}
void update(int i, ii nv) {
if (s != e) {
if (i > m) {
if (r == NULL) r = new maxseg(m + 1, e);
r -> update(i, nv);
} else {
if (l == NULL) l = new maxseg(s, m);
l -> update(i, nv);
}
v = max(l == NULL ? ii(0, -1) : l -> v, r == NULL ? ii(0, -1) : r -> v);
} else v = nv;
}
ii query(int a, int b) {
if (s == a && e == b) return v;
if (a > m) return r == NULL ? ii(0, -1) : r -> query(a, b);
if (b <= m) return l == NULL ? ii(0, -1) : l -> query(a, b);
return max(l == NULL ? ii(0, -1) : l -> query(a, m), r == NULL ? ii(0, -1) : r -> query(m + 1, b));
}
};
struct maxseg2d {
int s, e, m;
maxseg *v;
maxseg2d *l, *r;
maxseg2d(int rs, int re, int cs, int ce) {
s = rs, e = re, m = (s + e) / 2;
v = new maxseg(cs, ce);
l = r = NULL;
}
void update(int R, int C, ii nv) {
if (s != e) {
if (R > m) {
if (r == NULL) r = new maxseg2d(m + 1, e, v -> s, v -> e);
r -> update(R, C, nv);
} else {
if (l == NULL) l = new maxseg2d(s, m, v -> s, v -> e);
l -> update(R, C, nv);
}
v -> update(C, max(l == NULL ? ii(0, -1) : l -> v -> query(C, C), r == NULL ? ii(0, -1) : r -> v -> query(C, C)));
} else v -> update(C, nv);
}
ii query(int rs, int re, int cs, int ce) {
if (s == rs && e == re) return v -> query(cs, ce);
if (rs > m) return r == NULL ? ii(0, -1) : r -> query(rs, re, cs, ce);
if (re <= m) return l == NULL ? ii(0, -1) : l -> query(rs, re, cs, ce);
return max(l == NULL ? ii(0, -1) : l -> query(rs, m, cs, ce), r == NULL ? ii(0, -1) : r -> query(m + 1, re, cs, ce));
}
};
bool comp(const iii &a, const iii &b) {
if (a.first.second != b.first.second) return a.first.second < b.first.second;
return a < b;
}
int main() {
set<ii> poses;
int N;
scanf("%d", &N);
iii xy[N];
ii pos[N];
minseg2d *minx = new minseg2d(1, 100000, 1, 100000), *miny = new minseg2d(1, 100000, 1, 100000);
maxseg2d *maxx = new maxseg2d(1, 100000, 1, 100000), *maxy = new maxseg2d(1, 100000, 1, 100000);
for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i, poses.insert(pos[i]);
assert(poses.size() == N);
sort(xy, xy + N);
int xf[N], yf[N];
xf[xy[0].second] = -1;
for (int i = 1; i < N; ++i) {
if (xy[i - 1].first.first == xy[i].first.first) xf[xy[i - 1].second] = xy[i].second, xf[xy[i].second] = xy[i - 1].second;
else xf[xy[i].second] = -1;
}
sort(xy, xy + N, comp);
yf[xy[0].second] = -1;
for (int i = 1; i < N; ++i) {
if (xy[i - 1].first.second == xy[i].first.second) yf[xy[i - 1].second] = xy[i].second, yf[xy[i].second] = xy[i - 1].second;
else yf[xy[i].second] = -1;
}
queue<int> despo;
for (int i = 0; i < N; ++i) {
if (xf[i] == -1 && yf[i] == -1) {
printf("NE");
return 0;
} else if (xf[i] == -1 || yf[i] == -1) despo.push(i);
if (xf[i] != -1) minx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].first, i)), maxx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].first, i));
if (yf[i] != -1) miny -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].second, i)), maxy -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].second, i));
}
vector<ii> pairs;
bool settled[N];
fill_n(settled, N, false);
while (!despo.empty()) {
int pt1 = despo.front(), pt2;
despo.pop();
if (settled[pt1]) continue;
if (xf[pt1] != -1) {
pt2 = xf[pt1];
minx -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxx -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
if (yf[pt2] != -1) {
miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
miny -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(INF, -1)), maxy -> update(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(0, -1));
yf[yf[pt2]] = -1;
if (xf[yf[pt2]] == -1) {
printf("NE");
return 0;
} else despo.push(yf[pt2]);
}
ii qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
while (qans.first > pos[pt1].first) {
miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
yf[qans.second] = -1;
if (xf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = maxy -> query(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
}
qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
while (qans.first < pos[pt1].first) {
miny -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxy -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
yf[qans.second] = -1;
if (xf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = miny -> query(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
}
} else {
pt2 = yf[pt1];
miny -> update(pos[pt1].first, pos[pt1].second, ii(INF, -1)), maxy -> update(pos[pt1].first, pos[pt1].second, ii(0, -1));
miny -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxy -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
if (xf[pt2] != -1) {
minx -> update(pos[pt2].first, pos[pt2].second, ii(INF, -1)), maxx -> update(pos[pt2].first, pos[pt2].second, ii(0, -1));
minx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(INF, -1)), maxx -> update(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(0, -1));
xf[xf[pt2]] = -1;
if (yf[xf[pt2]] == -1) {
printf("NE");
return 0;
} else despo.push(xf[pt2]);
}
ii qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
while (qans.first > pos[pt1].second) {
minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
xf[qans.second] = -1;
if (yf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = maxx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
}
qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
while (qans.first < pos[pt1].second) {
minx -> update(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), maxx -> update(pos[qans.second].first, pos[qans.second].second, ii(0, -1));
xf[qans.second] = -1;
if (yf[qans.second] == -1) {
printf("NE");
return 0;
} else despo.push(qans.second);
qans = minx -> query(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), pos[pt1].second + 1, 100000);
}
}
pairs.push_back(ii(pt1, pt2));
settled[pt1] = settled[pt2] = true;
}
for (int i = 0; i < N; ++i) {
if (!settled[i]) pairs.push_back(ii(i, xf[i])), settled[i] = settled[xf[i]] = true;
}
printf("DA\n");
for (ii i: pairs) printf("%d %d\n", i.first + 1, i.second + 1);
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from matching.cpp:5:
matching.cpp: In function 'int main()':
matching.cpp:135:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(poses.size() == N);
~~~~~~~~~~~~~^~~~
matching.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
matching.cpp:134:115: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%d %d", &pos[i].first, &pos[i].second), xy[i].first = pos[i], xy[i].second = i, poses.insert(pos[i]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matching.cpp:159:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
bool settled[N];
^~~~~~~
matching.cpp:159:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1280 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
1280 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
