oj.uz

Submission #223426

# Submission time Handle Problem Language Result Execution time Memory
223426 2020-04-15T09:06:18 Z shenxy Matching (COCI20_matching) C++11
58 / 110
 1790 ms 524292 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
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() {
	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;
	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]].second, i)), maxx -> update(pos[i].first, pos[i].second, ii(pos[xf[i]].second, i));
		if (yf[i] != -1) miny -> update(pos[i].first, pos[i].second, ii(pos[yf[i]].first, i)), maxy -> update(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];
			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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct

Subtask #2
6.0 / 6.0

# 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 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct

Subtask #3
7.0 / 7.0

# 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 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 8 ms 2176 KB Output is correct
9 Correct 8 ms 2176 KB Output is correct
10 Correct 8 ms 2176 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct

Subtask #4
40.0 / 40.0

# 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 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 8 ms 2176 KB Output is correct
9 Correct 8 ms 2176 KB Output is correct
10 Correct 8 ms 2176 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 151 ms 58488 KB Output is correct
14 Correct 151 ms 58744 KB Output is correct
15 Correct 160 ms 57968 KB Output is correct
16 Correct 151 ms 58232 KB Output is correct
17 Correct 159 ms 57848 KB Output is correct
18 Correct 144 ms 58744 KB Output is correct
19 Correct 153 ms 58636 KB Output is correct
20 Correct 145 ms 58232 KB Output is correct
21 Correct 152 ms 58360 KB Output is correct
22 Correct 139 ms 58488 KB Output is correct
23 Correct 196 ms 58788 KB Output is correct
24 Correct 200 ms 58744 KB Output is correct

Subtask #5
0 / 52.0

# 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 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 8 ms 2176 KB Output is correct
9 Correct 8 ms 2176 KB Output is correct
10 Correct 8 ms 2176 KB Output is correct
11 Correct 8 ms 2176 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 151 ms 58488 KB Output is correct
14 Correct 151 ms 58744 KB Output is correct
15 Correct 160 ms 57968 KB Output is correct
16 Correct 151 ms 58232 KB Output is correct
17 Correct 159 ms 57848 KB Output is correct
18 Correct 144 ms 58744 KB Output is correct
19 Correct 153 ms 58636 KB Output is correct
20 Correct 145 ms 58232 KB Output is correct
21 Correct 152 ms 58360 KB Output is correct
22 Correct 139 ms 58488 KB Output is correct
23 Correct 196 ms 58788 KB Output is correct
24 Correct 200 ms 58744 KB Output is correct
25 Runtime error 1790 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -