Submission #559869

#	Time	Username	Problem	Language	Result	Execution time	Memory
559869		AlperenT	Comparing Plants (IOI20_plants)	C++17	5 / 100	76 ms	8796 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

int subtask = 0, n;

vector<array<int, 2>> prefix;

void init(int k, vector<int> r){
	n = r.size();
	if(k == 2) subtask = 1;

	prefix.assign(n, array{0, 0});

	if(r[0] == 0) prefix[0][0] = 1;
	else if(r[0] == 1) prefix[0][1] = 1;

	for(int i = 1; i < n; i++){
		prefix[i] = prefix[i - 1];

		if(r[i] == 0) prefix[i][0]++;
		else if(r[i] == 1) prefix[i][1]++;
	}
}

int compare_plants(int x, int y){
	int cnt0 = prefix[y - 1][0] - (x != 0 ? prefix[x - 1][0] : 0);
	int cnt1 = prefix[y - 1][1] - (x != 0 ? prefix[x - 1][1] : 0);

	if(cnt0 == 0) return -1;
	else if(cnt1 == 0) return 1;

	cnt0 = prefix[n - 1][0] - cnt0;
	cnt1 = prefix[n - 1][1] - cnt1;

	if(cnt0 == 0) return 1;
	else if(cnt1 == 0) 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