#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
using namespace std;
typedef long long ll;
int x[N], y[N], a[N][2], n, xr[N], yr[N];
set <int> tx[N * 4], ty[N * 4];
set <pair <int, pair <int, int> > > tx_del[N * 4], ty_del[N * 4];
vector <int> pshx[N * 4], pshy[N * 4];
vector <pair <int, pair <int, int> > > pshx_del[N * 4], pshy_del[N * 4], pshx_add[N * 4], pshy_add[N * 4];
bool mk[N], mkr[N][2];
queue <pair <int, int> > qr;
queue <int> alone;
vector <pair <int, int> > g;
void Push(int v, int tl, int tr)
{
while (sz(pshx[v]) > 0)
{
int val = pshx[v].back();
pshx[v].pop_back();
tx[v].insert(val);
if (tl != tr) {pshx[v + v].pb(val); pshx[v + v + 1].pb(val);}
}
while (sz(pshy[v]) > 0)
{
int val = pshy[v].back();
pshy[v].pop_back();
ty[v].insert(val);
if (tl != tr) {pshy[v + v].pb(val); pshy[v + v + 1].pb(val);}
}
}
void upd(int v, int tl, int tr, int l, int r, int val, bool f)
{
Push(v, tl, tr);
if (tl > tr || l > r || r < tl || tr < l) return;
if (l <= tl && tr <= r) {if (!f) pshx[v].pb(val); else pshy[v].pb(val); Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r, val, f);
upd(v + v + 1, md + 1, tr, l, r, val, f);
}
void Push_del(int v, int tl, int tr)
{
while (sz(pshx_add[v]) > 0)
{
pair <int, pair <int, int> > pt = pshx_add[v].back();
pshx_add[v].pop_back();
tx_del[v].insert(pt);
if (tl != tr) {pshx_add[v + v].pb(pt); pshx_add[v + v + 1].pb(pt); }
}
while (sz(pshy_add[v]) > 0)
{
pair <int, pair <int, int> > pt = pshy_add[v].back();
pshy_add[v].pop_back();
ty_del[v].insert(pt);
if (tl != tr) {pshy_add[v + v].pb(pt); pshy_add[v + v + 1].pb(pt); }
}
while (sz(pshx_del[v]) > 0)
{
pair <int, pair <int, int> > pt = pshx_del[v].back();
pshx_del[v].pop_back();
tx_del[v].erase(pt);
if (tl != tr) {pshx_del[v + v].pb(pt); pshx_del[v + v + 1].pb(pt); }
}
while (sz(pshy_del[v]) > 0)
{
pair <int, pair <int, int> > pt = pshy_del[v].back();
pshy_del[v].pop_back();
ty_del[v].erase(pt);
if (tl != tr) {pshy_del[v + v].pb(pt); pshy_del[v + v + 1].pb(pt);}
}
}
void upd_del(int v, int tl, int tr, int l, int r, pair <int, pair <int, int> > val, bool f)
{
Push_del(v, tl, tr);
if (tl > tr || l > r || r < tl || tr < l) return;
if (l <= tl && tr <= r) {if (!f) pshx_add[v].pb(val); else pshy_add[v].pb(val); Push_del(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd_del(v + v, tl, md, l, r, val, f);
upd_del(v + v + 1, md + 1, tr, l, r, val, f);
}
void upd_remove(int v, int tl, int tr, int l, int r, pair <int, pair <int, int> > val, bool f)
{
Push_del(v, tl, tr);
if (tl > tr || l > r || r < tl || tr < l) return;
if (l <= tl && tr <= r) {if (!f) pshx_del[v].pb(val); else pshy_del[v].pb(val); Push_del(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd_remove(v + v, tl, md, l, r, val, f);
upd_remove(v + v + 1, md + 1, tr, l, r, val, f);
}
bool good(int v, int tl, int tr, int pos, int l, int r, bool f)
{
Push(v, tl, tr);
if (tl == tr)
{
set <int> :: iterator it;
if (f)
{
it = ty[v].lower_bound(l);
return (it == ty[v].end() ? 1 : *it > r);
}
else
{
it = tx[v].lower_bound(l);
return (it == tx[v].end() ? 1 : *it > r);
}
}
else
{
int md = (tl + tr) >> 1;
if (pos <= md) return good(v + v, tl, md, pos, l, r, f);
return good(v + v + 1, md + 1, tr, pos, l, r, f);
}
}
pair <int, int> good_del(int v, int tl, int tr, int pos, int l, int r, bool f)
{
Push_del(v, tl, tr);
if (tl == tr)
{
set <pair <int, pair <int, int> > > :: iterator it;
if (f)
{
it = ty_del[v].lower_bound({l, {-1e9, -1e9}});
if (it == ty_del[v].end() || (*it).F > r) return {-1, -1};
return (*it).S;
}
else
{
it = tx_del[v].lower_bound({l, {-1e9, -1e9}});
if (it == tx_del[v].end() || (*it).F > r) return {-1, -1};
return (*it).S;
}
}
else
{
int md = (tl + tr) >> 1;
if (pos <= md) return good_del(v + v, tl, md, pos, l, r, f);
return good_del(v + v + 1, md + 1, tr, pos, l, r, f);
}
}
bool gd(int fr, int sc)
{
if (x[fr] == x[sc])
{
if (y[fr] > y[sc]) swap(fr, sc);
return good(1, 1, N - 1, x[fr], y[fr], y[sc], 0);
}
else
{
if (x[fr] > x[sc]) swap(fr, sc);
return good(1, 1, N - 1, y[fr], x[fr], x[sc], 1);
}
}
void add_remove(int fr, int sc)
{
if (!mk[fr]) alone.push(fr);
if (!mk[sc]) alone.push(sc);
if (x[fr] == x[sc])
{
if (y[fr] > y[sc]) swap(fr, sc);
upd_remove(1, 1, N, y[fr], y[sc], {x[fr], {fr, sc} }, 1);
}
else
{
if (x[fr] > x[sc]) swap(fr, sc);
upd_remove(1, 1, N, x[fr], x[sc], {y[fr], {fr, sc} }, 0);
}
}
void seacrh(int fr, int sc)
{
if (x[fr] == x[sc])
{
if (y[fr] > y[sc]) swap(fr, sc);
pair <int, int> pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);
while (pt.F != -1)
{
add_remove(pt.F, pt.S);
pt = good_del(1, 1, N, x[fr], y[fr], y[sc], 0);
}
}
else
{
if (x[fr] > x[sc]) swap(fr, sc);
pair <int, int> pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);
while (pt.F != -1)
{
add_remove(pt.F, pt.S);
pt = good_del(1, 1, N, y[fr], x[fr], x[sc], 1);
}
}
}
void add(int fr, int sc)
{
if (x[fr] == x[sc])
{
g.pb({fr, sc});
if (y[fr] > y[sc]) swap(fr, sc);
upd(1, 1, N - 1, y[fr], y[sc], x[fr], 1);
seacrh(fr, sc);
}
else
{
g.pb({fr, sc});
if (x[fr] > x[sc]) swap(fr, sc);
upd(1, 1, N - 1, x[fr], x[sc], y[fr], 0);
seacrh(fr, sc);
}
}
void clr(int x)
{
mk[x] = 1;
if (a[x][1] != -1) {if (!mk[a[x][1]]) alone.push(a[x][1]); a[x][1] = a[a[x][1]][1] = -1;}
if (a[x][0] != -1) {if (!mk[a[x][0]]) alone.push(a[x][0]); a[x][0] = a[a[x][0]][0] = -1;}
}
void fnd()
{
while (sz(alone) > 0)
{
int v = alone.front();
alone.pop();
if (mk[v]) continue;
if (a[v][1] != -1 && gd(v, a[v][1])) {qr.push({a[v][1], v}); a[v][1] = a[a[v][1]][1] = -1; return;}
if (a[v][0] != -1 && gd(v, a[v][0])) {qr.push({a[v][0], v}); a[v][0] = a[a[v][0]][0] = -1; return;}
cout << "NE" << endl;
exit(0);
}
for (int i = 0; i < n; i++)
{
if (mk[i]) continue;
g.pb({i, a[i][0]});
clr(a[i][0]);
clr(i);
}
}
void add_del(int fr, int sc)
{
if (x[fr] == x[sc])
{
if (mkr[fr][0]) return;
mkr[fr][0] = 1;
mkr[sc][0] = 1;
if (y[fr] > y[sc]) swap(fr, sc);
upd_del(1, 1, N, y[fr], y[sc], {x[fr], {fr, sc} }, 1);
}
else
{
if (mkr[fr][1]) return;
mkr[fr][1] = 1;
mkr[sc][1] = 1;
if (x[fr] > x[sc]) swap(fr, sc);
upd_del(1, 1, N, x[fr], x[sc], {y[fr], {fr, sc} }, 0);
}
}
int main()
{
freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < N; i++) xr[i] = yr[i] = -1;
for (int i = 0; i < n; i++) {cin >> x[i] >> y[i]; a[i][0] = a[i][1] = -1;}
for (int i = 0; i < n; i++)
{
int X = x[i], Y = y[i];
if (xr[X] == -1) xr[X] = i; else {a[i][0] = xr[X]; a[xr[X]][0] = i;}
if (yr[Y] == -1) yr[Y] = i; else {a[i][1] = yr[Y]; a[yr[Y]][1] = i;}
}
for (int i = 0; i < n; i++) if (a[i][0] == a[i][1] && a[i][1] == -1) {cout << "NE" << endl; exit(0);}
for (int i = 0; i < n; i++) if (a[i][0] == -1 || a[i][1] == -1) alone.push(i); else {add_del(i, a[i][0]); add_del(i, a[i][1]);}
fnd();
while (sz(qr) > 0)
{
int fr = qr.front().F;
int sc = qr.front().S;
qr.pop();
if (gd(fr, sc))
{
clr(fr);
clr(sc);
add(fr, sc);
}
fnd();
}
if (sz(g) != n / 2) {cout << "NE" << endl; exit(0);}
cout << "DA" << endl;
for (auto it : g) cout << it.F + 1 << " " << it.S + 1 << endl;
}
Compilation message
matching.cpp: In function 'int main()':
matching.cpp:377:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("in.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
132856 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
132856 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
132856 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
132856 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
132856 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
