Submission #223460

#	Time	Username	Problem	Language	Result	Execution time	Memory
223460		shenxy	Matching (COCI20_matching)	C++11	58 / 110	2605 ms	442644 KiB

matching

#include <cstdio>
#include <algorithm>
#include <queue>
#define m (s + e) / 2
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
const int INF = 10000000;
struct seg {
	int s, e;
	ii vmin, vmax;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e;
		vmin = ii(INF, -1), vmax = ii(0, -1);
		l = r = NULL;
	}
	void upmin(int i, ii nv) {
		if (s != e) {
			if (i > m) {
				if (r == NULL) r = new seg(m + 1, e);
				r -> upmin(i, nv);
			} else {
				if (l == NULL) l = new seg(s, m);
				l -> upmin(i, nv);
			}
			vmin = min(l == NULL ? ii(INF, -1) : l -> vmin, r == NULL ? ii(INF, -1) : r -> vmin);
		} else vmin = nv;
	}
	void upmax(int i, ii nv) {
		if (s != e) {
			if (i > m) {
				if (r == NULL) r = new seg(m + 1, e);
				r -> upmax(i, nv);
			} else {
				if (l == NULL) l = new seg(s, m);
				l -> upmax(i, nv);
			}
			vmax = max(l == NULL ? ii(0, -1) : l -> vmax, r == NULL ? ii(0, -1) : r -> vmax);
		} else vmax = nv;
	}
	ii qmin(int a, int b) {
		if (s == a && e == b) return vmin;
		if (a > m) return r == NULL ? ii(INF, -1) : r -> qmin(a, b);
		if (b <= m) return l == NULL ? ii(INF, -1) : l -> qmin(a, b);
		return min(l == NULL ? ii(INF, -1) : l -> qmin(a, m), r == NULL ? ii(INF, -1) : r -> qmin(m + 1, b));
	}
	ii qmax(int a, int b) {
		if (s == a && e == b) return vmax;
		if (a > m) return r == NULL ? ii(0, -1) : r -> qmax(a, b);
		if (b <= m) return l == NULL ? ii(0, -1) : l -> qmax(a, b);
		return max(l == NULL ? ii(0, -1) : l -> qmax(a, m), r == NULL ? ii(0, -1) : r -> qmax(m + 1, b));
	}
};
struct seg2d {
	int s, e;
	seg *v;
	seg2d *l, *r;
	seg2d(int rs, int re, int cs, int ce) {
		s = rs, e = re;
		v = new seg(cs, ce);
		l = r = NULL;
	}
	void upmin(int R, int C, ii nv) {
		if (s != e) {
			if (R > m) {
				if (r == NULL) r = new seg2d(m + 1, e, v -> s, v -> e);
				r -> upmin(R, C, nv);
			} else {
				if (l == NULL) l = new seg2d(s, m, v -> s, v -> e);
				l -> upmin(R, C, nv);
			}
			v -> upmin(C, min(l == NULL ? ii(INF, -1) : l -> v -> qmin(C, C), r == NULL ? ii(INF, -1) : r -> v -> qmin(C, C)));
		} else v -> upmin(C, nv);
	}
	void upmax(int R, int C, ii nv) {
		if (s != e) {
			if (R > m) {
				if (r == NULL) r = new seg2d(m + 1, e, v -> s, v -> e);
				r -> upmax(R, C, nv);
			} else {
				if (l == NULL) l = new seg2d(s, m, v -> s, v -> e);
				l -> upmax(R, C, nv);
			}
			v -> upmax(C, max(l == NULL ? ii(0, -1) : l -> v -> qmax(C, C), r == NULL ? ii(0, -1) : r -> v -> qmax(C, C)));
		} else v -> upmax(C, nv);
	}
	ii qmin(int rs, int re, int cs, int ce) {
		if (s == rs && e == re) return v -> qmin(cs, ce);
		if (rs > m) return r == NULL ? ii(INF, -1) : r -> qmin(rs, re, cs, ce);
		if (re <= m) return l == NULL ? ii(INF, -1) : l -> qmin(rs, re, cs, ce);
		return min(l == NULL ? ii(INF, -1) : l -> qmin(rs, m, cs, ce), r == NULL ? ii(INF, -1) : r -> qmin(m + 1, re, cs, ce));
	}
	ii qmax(int rs, int re, int cs, int ce) {
		if (s == rs && e == re) return v -> qmax(cs, ce);
		if (rs > m) return r == NULL ? ii(0, -1) : r -> qmax(rs, re, cs, ce);
		if (re <= m) return l == NULL ? ii(0, -1) : l -> qmax(rs, re, cs, ce);
		return max(l == NULL ? ii(0, -1) : l -> qmax(rs, m, cs, ce), r == NULL ? ii(0, -1) : r -> qmax(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() {
	int N;
	scanf("%d", &N);
	iii xy[N];
	ii pos[N];
	seg2d *x = new seg2d(1, 100000, 1, 100000), *y = new seg2d(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;
	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) x -> upmin(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i)), x -> upmax(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i));
		if (yf[i] != -1) y -> upmin(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i)), y -> upmax(pos[i].first, pos[i].second, ii(pos[yf[i]].first, 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];
			x -> upmin(pos[pt1].first, pos[pt1].second, ii(INF, -1)), x -> upmax(pos[pt1].first, pos[pt1].second, ii(0, -1));
			x -> upmin(pos[pt2].first, pos[pt2].second, ii(INF, -1)), x -> upmax(pos[pt2].first, pos[pt2].second, ii(0, -1));
			if (yf[pt2] != -1) {
				y -> upmin(pos[pt2].first, pos[pt2].second, ii(INF, -1)), y -> upmax(pos[pt2].first, pos[pt2].second, ii(0, -1));
				y -> upmin(pos[yf[pt2]].first, pos[yf[pt2]].second, ii(INF, -1)), y -> upmax(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 = y -> qmax(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) {
				y -> upmin(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), y -> upmax(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 = y -> qmax(1, pos[pt1].first - 1, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			}
			qans = y -> qmin(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) {
				y -> upmin(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), y -> upmax(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 = y -> qmin(pos[pt1].first + 1, 100000, min(pos[pt1].second, pos[pt2].second), max(pos[pt1].second, pos[pt2].second));
			}
		} else {
			pt2 = yf[pt1];
			y -> upmin(pos[pt1].first, pos[pt1].second, ii(INF, -1)), y -> upmax(pos[pt1].first, pos[pt1].second, ii(0, -1));
			y -> upmin(pos[pt2].first, pos[pt2].second, ii(INF, -1)), y -> upmax(pos[pt1].first, pos[pt1].second, ii(0, -1));
			if (xf[pt2] != -1) {
				x -> upmin(pos[pt2].first, pos[pt2].second, ii(INF, -1)), x -> upmax(pos[pt2].first, pos[pt2].second, ii(0, -1));
 				x -> upmin(pos[xf[pt2]].first, pos[xf[pt2]].second, ii(INF, -1)), x -> upmax(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 = x -> qmax(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) {
				x -> upmin(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), x -> upmax(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 = x -> qmax(min(pos[pt1].first, pos[pt2].first), max(pos[pt1].first, pos[pt2].first), 1, pos[pt1].second - 1);
			}
			qans = x -> qmin(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) {
				x -> upmin(pos[qans.second].first, pos[qans.second].second, ii(INF, -1)), x -> upmax(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 = x -> qmin(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 (stderr)

matching.cpp: In function 'int main()':
matching.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:111:97: 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;
                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
matching.cpp:135:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool settled[N];
       ^~~~~~~
matching.cpp:135:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52