oj.uz

Submission #223424

# Submission time Handle Problem Language Result Execution time Memory
223424 2020-04-15T09:05:20 Z shenxy Matching (COCI20_matching) C++11
58 / 110
 1647 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);
		if (s != e) {
			l = new minseg2d(rs, m, cs, ce);
			r = new minseg2d(m + 1, re, cs, ce);
		}
	}
	void update(int R, int C, ii nv) {
		if (s != e) {
			if (R > m) r -> update(R, C, nv);
			else l -> update(R, C, nv);
			v -> update(C, min(l -> v -> query(C, C), 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 -> query(rs, re, cs, ce);
		if (re <= m) return l -> query(rs, re, cs, ce);
		return min(l -> query(rs, m, cs, ce), 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);
		if (s != e) {
			l = new maxseg2d(rs, m, cs, ce);
			r = new maxseg2d(m + 1, re, cs, ce);
		}
	}
	void update(int R, int C, ii nv) {
		if (s != e) {
			if (R > m) r -> update(R, C, nv);
			else l -> update(R, C, nv);
			v -> update(C, max(l -> v -> query(C, C), 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 -> query(rs, re, cs, ce);
		if (re <= m) return l -> query(rs, re, cs, ce);
		return max(l -> query(rs, m, cs, ce), 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:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:127: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:151:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool settled[N];
       ^~~~~~~
matching.cpp:151: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 80 ms 76408 KB Output is correct
2 Correct 84 ms 76572 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76408 KB Output is correct
2 Correct 84 ms 76572 KB Output is correct
3 Correct 78 ms 76408 KB Output is correct
4 Correct 79 ms 76408 KB Output is correct
5 Correct 78 ms 76396 KB Output is correct
6 Correct 77 ms 76280 KB Output is correct
7 Correct 102 ms 76364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76408 KB Output is correct
2 Correct 84 ms 76572 KB Output is correct
3 Correct 78 ms 76408 KB Output is correct
4 Correct 79 ms 76408 KB Output is correct
5 Correct 78 ms 76396 KB Output is correct
6 Correct 77 ms 76280 KB Output is correct
7 Correct 102 ms 76364 KB Output is correct
8 Correct 83 ms 77304 KB Output is correct
9 Correct 84 ms 77176 KB Output is correct
10 Correct 83 ms 77176 KB Output is correct
11 Correct 81 ms 77304 KB Output is correct
12 Correct 83 ms 77304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76408 KB Output is correct
2 Correct 84 ms 76572 KB Output is correct
3 Correct 78 ms 76408 KB Output is correct
4 Correct 79 ms 76408 KB Output is correct
5 Correct 78 ms 76396 KB Output is correct
6 Correct 77 ms 76280 KB Output is correct
7 Correct 102 ms 76364 KB Output is correct
8 Correct 83 ms 77304 KB Output is correct
9 Correct 84 ms 77176 KB Output is correct
10 Correct 83 ms 77176 KB Output is correct
11 Correct 81 ms 77304 KB Output is correct
12 Correct 83 ms 77304 KB Output is correct
13 Correct 222 ms 130680 KB Output is correct
14 Correct 242 ms 131064 KB Output is correct
15 Correct 240 ms 130332 KB Output is correct
16 Correct 228 ms 130680 KB Output is correct
17 Correct 237 ms 130168 KB Output is correct
18 Correct 223 ms 131064 KB Output is correct
19 Correct 224 ms 130936 KB Output is correct
20 Correct 224 ms 130552 KB Output is correct
21 Correct 220 ms 130680 KB Output is correct
22 Correct 217 ms 130680 KB Output is correct
23 Correct 280 ms 131704 KB Output is correct
24 Correct 277 ms 131320 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76408 KB Output is correct
2 Correct 84 ms 76572 KB Output is correct
3 Correct 78 ms 76408 KB Output is correct
4 Correct 79 ms 76408 KB Output is correct
5 Correct 78 ms 76396 KB Output is correct
6 Correct 77 ms 76280 KB Output is correct
7 Correct 102 ms 76364 KB Output is correct
8 Correct 83 ms 77304 KB Output is correct
9 Correct 84 ms 77176 KB Output is correct
10 Correct 83 ms 77176 KB Output is correct
11 Correct 81 ms 77304 KB Output is correct
12 Correct 83 ms 77304 KB Output is correct
13 Correct 222 ms 130680 KB Output is correct
14 Correct 242 ms 131064 KB Output is correct
15 Correct 240 ms 130332 KB Output is correct
16 Correct 228 ms 130680 KB Output is correct
17 Correct 237 ms 130168 KB Output is correct
18 Correct 223 ms 131064 KB Output is correct
19 Correct 224 ms 130936 KB Output is correct
20 Correct 224 ms 130552 KB Output is correct
21 Correct 220 ms 130680 KB Output is correct
22 Correct 217 ms 130680 KB Output is correct
23 Correct 280 ms 131704 KB Output is correct
24 Correct 277 ms 131320 KB Output is correct
25 Runtime error 1647 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -