Submission #1043227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043227		thinknoexit	Comparing Plants (IOI20_plants)	C++17	19 / 100	4093 ms	9584 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n, k;
int ord[N], deg[N], dpl[N], dpr[N];
void init(int K, vector<int> r) {
	n = r.size();
	k = K;
	if (k == 2) {
		for (int i = 0;i < n;i++) {
			if (r[i] == 1) deg[(i + 1) % n]++;
			else deg[i]++;
		}
		for (int i = 0;i < n;i++) {
			if (deg[i] != 0) continue;
			dpl[i] = dpr[i] = 0;
			for (int j = 1;j < n;j++) {
				dpr[(i - j + n) % n] = j;
				if (deg[(i - j + n) % n] == 2) break;
			}
			for (int j = 1;j < n;j++) {
				dpl[(i + j) % n] = j;
				if (deg[(i + j) % n] == 2) break;
			}
		}
		return;
	}
	memset(ord, -1, sizeof ord);
	for (int i = n;i >= 1;i--) {
		vector<int> v;
		for (int j = 0;j < n;j++) {
			if (ord[j] == -1 && r[j] == 0) {
				v.push_back(j);
			}
		}
		int sz = v.size();
		int idx = v[0];
		for (int j = 1;j < sz;j++) {
			if (v[j] - v[j - 1] >= k) idx = v[j];
		}
		ord[idx] = i;
		for (int j = 1;j < k;j++) {
			r[(idx - j + n) % n]--;
		}
	}
}
bool can(int x, int y) {
	int l = dpr[x], r = dpl[x];
	if (x + l >= n) {
		if (x <= y || y <= x + l - n) return 1;
	}
	else {
		if (x <= y && y <= x + l) return 1;
	}
	if (x - r < 0) {
		if (y <= x || n + x - r <= y) return 1;
	}
	else {
		if (x - r <= y && y <= x) return 1;
	}
	return 0;
}
int compare_plants(int x, int y) {
	if (k != 2) return (ord[x] > ord[y]) ? 1 : -1;
	if (can(x, y)) return 1;
	if (can(y, x)) return -1;
	return 0;
}

• Subtask 1: 5 / 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