Submission #1205193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205193		bangan	Comparing Plants (IOI20_plants)	C++20	11 / 100	65 ms	3212 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

struct Node {
	int pos, val;
	Node(int pos_ = 0, int val_ = 0): pos(pos_), val(val_) {}

	Node friend operator+ (Node a, Node b) {
		if (a.val == b.val) {
			return a.pos < b.pos ? a : b;
		} else {
			return a.val < b.val ? a : b;
		}
	}
};

struct SegmentTree {
	#define lc (v << 1)
	#define rc (v << 1 | 1)
	#define mid (l + r) / 2

	int n;
	std::vector<Node> a;
	std::vector<int> b;
	SegmentTree(int n_): n(n_), a(4 * n + 1), b(4 * n + 1, 0) {}

	void push(int v) {
		if (a[v].val != n) {
			a[v].val += b[v];
		}
		if (lc <= 4 * n) {
			b[lc] += b[v];
		}
		if (rc <= 4 * n) {
			b[rc] += b[v];
		}
		b[v] = 0;
	}

	void set_val(int i, int x, int v, int l, int r) {
		push(v);
		if (r - l == 1) {
			a[v] = Node(i, x);
			return;
		}

		i < mid ? set_val(i, x, lc, l, mid) : set_val(i, x, rc, mid, r);

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void set_val(int i, int x) {
		set_val(i, x, 1, 0, n);
	}

	void update(int s, int e, int x, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			b[v] += x;
			push(v);
			return;
		}

		if (s < mid) {
			update(s, e, x, lc, l, mid);
		}
		if (e > mid) {
			update(s, e, x, rc, mid, r);
		}

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void update(int s, int e, int x) {
		update(s, e, x, 1, 0, n);
	};

	Node get(int s, int e, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			return a[v];
		}

		if (e <= mid) {
			return get(s, e, lc, l, mid);
		} else if (s >= mid) {
			return get(s, e, rc, mid, r);
		} else {
			return get(s, e, lc, l, mid) + get(s, e, rc, mid, r);
		}
	}
	Node get(int s, int e) {
		return get(s, e, 1, 0, n);
	}
};

constexpr int N = 300;

int n, h[N];
std::bitset<N> can[N];

void init(int k, std::vector<int> org_r) {
	n = org_r.size();
	assert(n <= 300);

	auto norm = [&](int i) {
		i %= n;
		if (i < 0) {
			return i + n;
		} else {
			return i;
		}
	};

	SegmentTree r(n);
	for (int i = 0; i < n; i++) {
		r.set_val(i, org_r[i]);
	}
	auto get = [&](int s, int e) -> Node {
		s = norm(s);
		e = norm(e);
		// std::cout << "(s, e) = (" << s << ", " << e << ")\n";
		if (s <= e) {
			return r.get(s, e + 1);
		} else {
			return r.get(s, n) + r.get(0, e + 1);
		}
	};
	auto update = [&](int s, int e, int x) {
		s = norm(s);
		e = norm(e);
		if (s <= e) {
			r.update(s, e + 1, x);
		} else {
			r.update(s, n, x);
			r.update(0, e + 1, x);
		}
	};

	std::vector<int> ord;
	auto dec = [&](auto self, int i) -> void {
		while (get(i - k + 1, i - 1).val == 0) {
			self(self, get(i - k + 1, i - 1).pos);
		}

		ord.push_back(i);
		r.set_val(i, n);
		update(i - k + 1, i - 1, -1);
	};
	while (get(0, n - 1).val < n) {
		int i = get(0, n - 1).pos;
		dec(dec, i);
	}
	for (int i = 0; i < n; i++) {
		h[ord[i]] = n - i - 1;
	}

	auto d = [&](int i, int j) {
		if (i > j) {
			std::swap(i, j);
		}
		return std::min(j - i, n - j + i);
	};

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d(i, j) < k && h[i] > h[j]) {
				can[i][j] = true;
			}
		}
	}

	for (int stp = 0; stp < n; stp++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				can[i][j] = can[i][j] || (can[i][stp] && can[stp][j]);
			}
		}
	}

	return;
}

int compare_plants(int x, int y) {
	if (can[x][y] == can[y][x]) {
		return 0;
	} else if (can[x][y]) {
		return 1;
	} else {
		return -1;
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25