Submission #434785

#	Time	Username	Problem	Language	Result	Execution time	Memory
434785		rqi	Comparing Plants (IOI20_plants)	C++14	19 / 100	4077 ms	8400 KiB

plants

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

typedef vector<int> vi;
typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

const int mx = 200005;

int k;
vi r;
int n;
pi rangs[mx][2];

void doK2Init(){
	int start = 0;
	for(int i = 0; i < n; i++){
		if(r[i] != r[0]){
			start = i;
			break;
		}
	}

	int cur = start;

	while(true){
		int end_ind = cur;
		while(r[(end_ind+1) % n] == r[cur]){
			end_ind = (end_ind+1) % n;
		}

		pi interval = mp(cur, (end_ind+1) % n);

		// cout << cur << " " << end_ind << "\n";
		// cout << interval.f << " " << interval.s << "\n";
		for(int i = cur; ; (i = (i+1) % n)){
			if(i == cur){
				rangs[i][1] = mp(r[cur], interval.s);
			}
			else if(i == (end_ind+1) % n){
				rangs[i][0] = mp(r[cur], interval.f);
				break;
			}
			else{
				rangs[i][0] = mp(r[cur], interval.f);
				rangs[i][1] = mp(r[cur], interval.s);
			}
		}

		cur = (end_ind+1) % n;
		if(cur == start) break;
	}

	return;
}

int val[mx];

void init(int _k, vi _r) {
	k = _k;
	r = _r;
	n = sz(r);

	if(k == 2){
		doK2Init();
		return;
	}
		
	for(int i = 0; i < n; i++){
		val[i] = -1;
	}
	for(int i = n-1; i >= 0; i--){
		int cur_pos = -1;
		for(int j = 0; j < n; j++){
			if(val[j] != -1) continue;
			if(r[j] == 0){
				// cout << "j: " << j << "\n";
				if(cur_pos == -1){
					cur_pos = j;
				}
				else{
					if((j-cur_pos)*2 > n){
						cur_pos = j;
					}
				}
			}
		}
		// cout << i << " " << cur_pos << "\n";
		assert(cur_pos != -1);
		val[cur_pos] = i;

		for(int j = 0; j <= k-1; j++){
			// cout << (cur_pos-j+n) % n << "\n";
			r[(cur_pos-j+n) % n]--;
		}

		// for(int j = 0; j < n; j++){
		// 	cout << "j, r[j]: " << j << " " << r[j] << "\n";
		// }
	}
}

bool isInInterval(int test, int int_beg, int int_end){
	if(int_beg <= int_end){
		return (int_beg <= test) && (test <= int_end);
	}

	return (int_beg <= test) || (test <= int_end);
}

int doK2Compare(int x, int y){
	if(isInInterval(y, rangs[x][0].s, x)){
		if(rangs[x][0].f == 1){
			return 1;
		}
		else{
			return -1;
		}
	}
	else if(isInInterval(y, x, rangs[x][1].s)){
		if(rangs[x][1].f == 1){
			return -1;
		}
		else{
			return 1;
		}
	}
	return 0;
}

int compare_plants(int x, int y) {
	if(k == 2){
		return doK2Compare(x, y);
	}

	if(val[x] < val[y]) return -1;
	
	return 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