Submission #1050236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050236		TahirAliyev	Comparing Plants (IOI20_plants)	C++17	14 / 100	100 ms	9964 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 5005;
int id[MAX];
int pre[MAX];
int n;
int ask(int l, int r){
	if(r < l){
		return pre[n] - (pre[l - 1] - pre[r]);
	}
	return pre[r] - pre[l - 1];
}
void init(int k, vector<int> r) {
	n = r.size();
	vector<int> zer;
	r.insert(r.begin(), 0);
	for(int i = 1; i <= n; i++){
		if(!r[i]) zer.push_back(i);
	}
	int t = n;
	while(zer.size()){
		for(int i = 1; i <= n; i++){
			pre[i] = pre[i - 1] + (!r[i]);
		}
		int f = 0, l = 0;
		for(int a : zer){
			l = a - k + 1;
			if(l <= 0) l += n;
			if(!ask(l, a - 1)){
				f = a;
				break;
			}
		}
		l = f - k + 1;
		if(l <= 0) l += n;
		r[f] = 1e9;
		id[f] = t--;
		for(int i = l; ; i++){
			if(i == f) break;
			if(i > n){
				i = 0;
				continue;
			}
			r[i]--;
			if(r[i] == 0) zer.push_back(i);
		}
		zer.erase(find(zer.begin(), zer.end(), f));
	}
	// for(int i = 1; i <= n; i ++){
	// 	cout << id[i] << ' ';
	// }
	// cout << '\n';
}

int compare_plants(int x, int y) {
	x++, y++;
	if(id[x] > id[y]) return 1;
	else return -1;
}

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