Submission #612447

#	Time	Username	Problem	Language	Result	Execution time	Memory
612447		erekle	Comparing Plants (IOI20_plants)	C++17	5 / 100	87 ms	8688 KiB

plants

#include "plants.h"

using namespace std;

int n;
vector<int> greater, less;

void init(int k, vector<int> r) {
	n = r.size();
	greater.resize(n);
	less.resize(n);
	
	// find cross-over
	int start = 0;
	while (r[(start-1+n)%n] == r[start]) ++start;

	int cur = (start-1+n)%n;
	do {
		int nxt = (cur+1)%n;
		if (r[cur]) less[cur] = less[nxt]+1;
		else greater[cur] = greater[nxt]+1;
		cur = (cur-1+n)%n;
	} while ((cur+1)%n != start);
	return;
}

int compare_plants(int x, int y) {
	int sub = (x < y ? 0 : n);
	if (x+greater[x]-sub >= y) return 1;
	if (x+less[x]-sub >= y) return -1;
	sub = n-sub;
	if (y+greater[y]-sub >= x) return -1;
	if (y+less[y]-sub >= x) return 1;
	return 0;
}

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