Submission #227319

#	Time	Username	Problem	Language	Result	Execution time	Memory
227319		abeker	Matching (COCI20_matching)	C++17	110 / 110	967 ms	104332 KiB

matching

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e5 + 5;
const int offset = 1 << 17;

struct Segment {
	int x1, y1, x2, y2;
};

class Tournament {
	set <pii> S[2 * offset];
public:
	void update(int x, int lo, int hi, int from, int to, pii p) {
		if (lo >= to || hi <= from)
			return;
		if (lo >= from && hi <= to) {
			S[x].insert(p);
			return;
		}
		int mid = (lo + hi) / 2;
		update(2 * x, lo, mid, from, to, p);
		update(2 * x + 1, mid, hi, from, to, p);
	}
	vector <int> query(int x, int from, int to) {
		vector <int> res;
		for (x += offset; x; x /= 2)
			while (1) {
				auto it = S[x].lower_bound({from, 0});
				if (it == S[x].end() || it->first > to)
					break;
				res.push_back(it->second);
				S[x].erase(it);
			}
		return res;
	}
};

int N;
int x[MAXN], y[MAXN];
vector <int> adj[MAXN];
vector <int> hor[MAXN], ver[MAXN];
vector <Segment> all;
vector <pii> edges;
Tournament Hor, Ver;
int clr[2 * MAXN];
queue <int> Q;

void load() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", x + i, y + i);
		ver[x[i]].push_back(i);
		hor[y[i]].push_back(i);
	}
}

void bye() {
	puts("NE");
	exit(0);
}

void process(const vector <int> &v, int c) {
	for (auto it : v) {
		if (clr[it] == -1)
			clr[it] = c;
		else if (clr[it] != c)
			bye();
		Q.push(it);
	}
}

void other(int pt, int seg) {
	if (adj[pt].size() == 1)
		bye();
	process({adj[pt][0] ^ adj[pt][1] ^ seg}, 1);
}

void horizontal(int id) {
	if (clr[id]) 
		process(Ver.query(all[id].y1, all[id].x1, all[id].x2), 0);
	else {
		other(edges[id].first, id);
		other(edges[id].second, id);
	}
}

void vertical(int id) {
	if (clr[id]) 
		process(Hor.query(all[id].x1, all[id].y1, all[id].y2), 0);
	else {
		other(edges[id].first, id);
		other(edges[id].second, id);
	}
}

inline bool is_hor(int id) {
	return all[id].y1 == all[id].y2;
}

void solve() {
	memset(clr, -1, sizeof clr);
	
	for (int i = 1; i < MAXN; i++) {
		if (hor[i].size() == 2) {
			int mn = MAXN, mx = 0;
			for (auto it : hor[i]) {
				adj[it].push_back(all.size());
				mn = min(mn, x[it]);
				mx = max(mx, x[it]);
			}
			Hor.update(1, 0, offset, mn, mx + 1, {i, all.size()});
			edges.push_back({hor[i][0], hor[i][1]});
			all.push_back({mn, i, mx, i});
		}
		if (ver[i].size() == 2) {
			int mn = MAXN, mx = 0;
			for (auto it : ver[i]) {
				adj[it].push_back(all.size());
				mn = min(mn, y[it]);
				mx = max(mx, y[it]);
			}
			Ver.update(1, 0, offset, mn, mx + 1, {i, all.size()});
			edges.push_back({ver[i][0], ver[i][1]});
			all.push_back({i, mn, i, mx});
		}
	}
	
	for (int i = 0; i < N; i++)
		if (adj[i].empty())
			bye();
		else if (adj[i].size() == 1) {
			clr[adj[i][0]] = 1;
			Q.push(adj[i][0]);
		}
	
	while (!Q.empty()) {
		int curr = Q.front();
		Q.pop();
		if (is_hor(curr))
			horizontal(curr);
		else
			vertical(curr);
	}
	
	puts("DA");
	for (int i = 0; i < all.size(); i++) {
		if (clr[i] == -1)
			clr[i] = is_hor(i);
		if (clr[i])
			printf("%d %d\n", ++edges[i].first, ++edges[i].second); 
	}
}

int main() {
	load();
	solve();
	return 0;
}

Compilation message (stderr)

matching.cpp: In function 'void solve()':
matching.cpp:149:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < all.size(); i++) {
                  ~~^~~~~~~~~~~~
matching.cpp: In function 'void load()':
matching.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
matching.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", x + i, y + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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