This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define LL long long
#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b - 1); ++i)
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define X first
#define Y second
#define pb push_back
#define ef else if
using namespace std;
const int mxn = 1e5 + 5;
const int mxk = 2e3 + 5;
const int INF = 1e9 + 7;
const LL base = 64319;
const LL MOD = 2928127154483;
vector<int> ox[mxn], oy[mxn], same_ox[mxn], same_oy[mxn];
int x[mxn], y[mxn];
vector<pii> res;
set<int> seg[4*mxn];
bool vis[mxn];
void update(int L, int R, int h, int l, int r, int pos)
{
if (r < L || R < l) return;
if (L <= l && r <= R)
{
seg[pos].insert(h);
return;
}
int mid = (l + r)>>1;
update(L, R, h, l, mid, pos << 1);
update(L, R, h, mid + 1, r, pos << 1 | 1);
}
bool get(int x, int L, int H, int l, int r, int pos)
{
if (x < l || r < x) return 0;
auto it = seg[pos].lower_bound(L);
if (it != seg[pos].end())
if (L <= *it && *it <= H) return 1;
if (l == r) return 0;
int mid = (l + r)>>1;
return (get(x, L, H, l, mid, pos << 1)||get(x, L, H, mid + 1, r, pos << 1 | 1));
}
int main()
{
//freopen("D:\\test.txt", "r", stdin);
//freopen("D:\\test2.txt", "w", stdout);
int n; cin >> n;
REP(i, 1, n)
{
scanf("%d%d", &x[i], &y[i]);
if (ox[x[i]].size() == 0) ox[x[i]].pb(i);
else
{
same_ox[i].pb(ox[x[i]].back());
same_ox[ox[x[i]].back()].pb(i);
ox[x[i]].pop_back();
}
if (oy[y[i]].size() == 0) oy[y[i]].pb(i);
else
{
same_oy[i].pb(oy[y[i]].back());
same_oy[oy[y[i]].back()].pb(i);
oy[y[i]].pop_back();
}
}
REP(i, 1, n) if (same_ox[i].size() == 0 && same_oy[i].size() == 0)
{
printf("NE");
return 0;
}
bool ok = 1;
REP(i, 1, n) if (same_ox[i].size() == 0) {ok = 0; break;}
if (ok)
{
printf("DA\n");
REP(u, 1, n) if (!vis[u])
{
int v = same_ox[u].back();
printf("%d %d\n", u, v);
vis[u] = vis[v] = 1;
}
return 0;
}
vector<int> de;
REP(i, 1, n) if (same_oy[i].size() == 1 && same_ox[i].size() == 0)
de.pb(i);
while(de.size())
{
int u = de.back(); de.pop_back();
if (vis[u]) continue;
vis[u] = 1;
int v = same_oy[u].back(); same_oy[u].pop_back();
res.pb({u, v}); vis[v] = 1;
same_oy[v].pop_back();
if (same_ox[v].size() != 0)
{
int k = same_ox[v].back();
same_ox[v].pop_back();
same_ox[k].pop_back();
if (same_oy[k].size() == 0)
{
printf("NE");
return 0;
}
else de.pb(k);
}
update(min(x[u], x[v]), max(x[u], x[v]), y[u], 1, mxn, 1);
}
REP(u, 1, n) if (!vis[u])
{
if (same_ox[u].size() == 0)
{
printf("NE");
return 0;
}
int v = same_ox[u].back(); same_ox[u].pop_back();
if (!get(x[u], min(y[v], y[u]), max(y[v], y[u]), 1, mxn, 1))
{
res.pb({u, v});
vis[u] = vis[v] = 1;
}
else
{
printf("NE");
return 0;
}
}
printf("DA\n");
for (pii t : res)
printf("%d %d\n", t.X, t.Y);
}
Compilation message (stderr)
matching.cpp: In function 'int main()':
matching.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d", &x[i], &y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |