Submission #302934

#	Time	Username	Problem	Language	Result	Execution time	Memory
302934		8e7	Comparing Plants (IOI20_plants)	C++14	5 / 100	116 ms	8684 KiB

plants

#include "plants.h"
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> v, one, zero, ind1, ind0;
int k;
int n;
void init(int K, vector<int> r) {
	v = r;
	n = r.size();
	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;
		}
	}
	k = K;
	/*
	for (int i = 0;i < n;i++) cout << one[i] << " ";
	cout << endl;
	for (int i:ind1) cout << i << " ";
	cout << endl;
	for (int i = 0;i < n;i++) cout << zero[i] << " ";
	cout << endl;
	for (int i:ind0) cout << i << " ";
	cout << endl;
	*/
	return;
}

int compare_plants(int x, int y) {
	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;
		}
	}
}
/*
5 1 3
1 1 0 0 1
0 1
0 3
2 4
 */

• 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