oj.uz

Submission #223429

# Submission time Handle Problem Language Result Execution time Memory
223429 2020-04-15T09:09:06 Z shenxy Matching (COCI20_matching) C++11
58 / 110
 1777 ms 524292 KB 
#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 minseg {
	int s, e;
	ii v;
	minseg *l, *r;
	minseg(int _s, int _e) {
		s = _s, e = _e;
		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;
	minseg *v;
	minseg2d *l, *r;
	minseg2d(int rs, int re, int cs, int ce) {
		s = rs, e = re;
		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;
	ii v;
	maxseg *l, *r;
	maxseg(int _s, int _e) {
		s = _s, e = _e;
		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;
	maxseg *v;
	maxseg2d *l, *r;
	maxseg2d(int rs, int re, int cs, int ce) {
		s = rs, e = re;
		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:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:132: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:156:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool settled[N];
       ^~~~~~~
matching.cpp:156: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 1328 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 1328 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 1328 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 7 ms 2176 KB Output is correct
11 Correct 7 ms 2176 KB Output is correct
12 Correct 9 ms 2304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1328 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 7 ms 2176 KB Output is correct
11 Correct 7 ms 2176 KB Output is correct
12 Correct 9 ms 2304 KB Output is correct
13 Correct 159 ms 58488 KB Output is correct
14 Correct 156 ms 58792 KB Output is correct
15 Correct 158 ms 57976 KB Output is correct
16 Correct 158 ms 58232 KB Output is correct
17 Correct 162 ms 57848 KB Output is correct
18 Correct 147 ms 58744 KB Output is correct
19 Correct 153 ms 58616 KB Output is correct
20 Correct 154 ms 58360 KB Output is correct
21 Correct 140 ms 58360 KB Output is correct
22 Correct 146 ms 58444 KB Output is correct
23 Correct 203 ms 58872 KB Output is correct
24 Correct 199 ms 58744 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1328 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 7 ms 2176 KB Output is correct
11 Correct 7 ms 2176 KB Output is correct
12 Correct 9 ms 2304 KB Output is correct
13 Correct 159 ms 58488 KB Output is correct
14 Correct 156 ms 58792 KB Output is correct
15 Correct 158 ms 57976 KB Output is correct
16 Correct 158 ms 58232 KB Output is correct
17 Correct 162 ms 57848 KB Output is correct
18 Correct 147 ms 58744 KB Output is correct
19 Correct 153 ms 58616 KB Output is correct
20 Correct 154 ms 58360 KB Output is correct
21 Correct 140 ms 58360 KB Output is correct
22 Correct 146 ms 58444 KB Output is correct
23 Correct 203 ms 58872 KB Output is correct
24 Correct 199 ms 58744 KB Output is correct
25 Runtime error 1777 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -