Submission #1242898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242898		Joshua_Andersson	Comparing Plants (IOI20_plants)	C++20	14 / 100	4094 ms	6216 KiB

plants

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

typedef long long ll;
const ll inf = 1e18;

typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> p2;

#define rep(i, high) for (ll i = 0; i < (high); i++)
#define repp(i, lo, high) for (ll i = (lo); i < (high); i++)
#define repe(i, container) for (auto& i : container)
#define sz(x) ((ll)(x).size())
#define all(x) begin(x), end(x)

vi real_heights;
void init(int k, std::vector<int> r) {
	int n = sz(r);
	real_heights.resize(n);


	auto norm = [&](int x)
		{
			if (x < 0) x %= n, x += n;
			if (x >= n) return x % n;
			return x;
		};

	auto find_zero = [&](int l, int qr)
		{
			repp(i, l, qr+1) if (r[norm(i)] == 0) return norm(i);
			return -1;
		};

	int ind = n - 1;
	rep(i, n)
	{
		int j = find_zero(0, n-1);
		if (j == -1) break;
		vi st = { j };
		while (sz(st))
		{
			int u = st.back();
			int v = find_zero(u - k + 1, u - 1);
			if (v == -1)
			{
				st.pop_back();
				real_heights[u] = ind--;
				repp(i, u - k + 1, u + 1) r[norm(i)]--;
			}
			else
			{
				st.push_back(v);
			}
		}
	}

	return;
}

int compare_plants(int x, int y) {
	if (real_heights[x] > real_heights[y]) return 1;
	return -1;
}

#if _LOCAL

static int n, k, q;
static std::vector<int> r;
static std::vector<int> x;
static std::vector<int> y;
static std::vector<int> answer;
int main() {
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif

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