Submission #302938

#	Time	Username	Problem	Language	Result	Execution time	Memory
302938		8e7	Comparing Plants (IOI20_plants)	C++14	19 / 100	4083 ms	9580 KiB

plants

#include "plants.h"
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> v, one, zero, ind1, ind0, arr;
int k;
int n;
void init(int K, vector<int> r) {
	v = r;
	n = r.size();
	arr.resize(n);
	k = K;
	if (K == 2) {
		int cnt = 0, cur = 0;
		one.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 0) {
				ind1.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			one.push_back(cnt);
		}
		if (r[n - 1] == 1) {
			for (int i = n - 1;i >= 0;i--) {
				if (one[i] == cnt) ind1[0] = i;
				one[i] %= cnt;
			}
		}
		cnt = 0, cur = 0;
		zero.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 1) {
				ind0.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			zero.push_back(cnt);
		}
		if (r[n - 1] == 0) {
			for (int i = n - 1;i >= 0;i--) {
				if (zero[i] == cnt) ind0[0] = i;
				zero[i] %= cnt;
			}
		}
	} else {
		for (int i = n;i >= 1;i--) {
			for (int j = n - 1;j >= 0;j--) {
				if (r[j] == 0) {
					int ind = (j - 1 + n) % n, found = 1;
					for (int cnt = 0;cnt < k - 1;cnt++) {
						if (r[ind] == 0) {
							found = 0;
							break;
						}
						ind = (ind - 1 + n) % n;
					}
					if (found) {
						arr[j] = i;
						int ind = (j + n) % n;
						for (int cnt = 0;cnt < k;cnt++) {
							r[ind]--;
							ind = (ind - 1 + n) % n;
						}

						//for (int i = 0;i < n;i++) cout << r[i] << " ";
						//cout << endl;
						break;
					}
				}
			}
		}
		//for (int i = 0;i < n;i++) cout << arr[i] << " ";
		//cout << endl;
	}
	return;
}

int compare_plants(int x, int y) {
	if (k == 2) {
		if (one[x] != one[y] && zero[x] != zero[y]) {
			return 0;
		} else {
			if (one[x] == one[y]) {
				//cout <<(x - ind1[one[x]] + n) % n << " " << (y - ind1[one[y]] + n) % n << endl;
				if ((x - ind1[one[x]] + n) % n < (y - ind1[one[y]] + n) % n) return -1;
				else return 1;
			} else {
				if ((x - ind0[zero[x]] + n) % n < (y - ind0[zero[y]] + n) % n) return 1;
				else return -1;
			}
		}
	} else {
		return arr[x] > arr[y] ? 1 : -1;
	}
}

• 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