Submission #432150

#	Time	Username	Problem	Language	Result	Execution time	Memory
432150		peuch	Comparing Plants (IOI20_plants)	C++17	5 / 100	100 ms	5880 KiB

plants

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

int N;
bool sub1;
vector<int> esq, dir;

void init(int k, vector<int> r) {
	sub1 = k == 2;
	N = r.size();
	if(sub1){
		esq = vector<int> (N);
		dir = vector<int> (N);
		int ini;
		for(ini = 0; ini < N; ini++)
			if(r[ini] == 0) break;
		ini++;
		ini %= N;
		esq[ini] = 0;
		for(int i = ini + 1; i != ini; i++, i %= N){
			int ant = i - 1;
			if(ant < 0) ant += N;
			esq[i] = esq[ant] + 1;
			if(r[ant] == 0) esq[i] = 0;
		}
		
		for(ini = 0; ini < N; ini++)
			if(r[ini] == 1) break;
		dir[ini] = 0;
		for(int i = (ini + N - 1) % N; i != ini; i += N - 1, i %= N){
			int nex = i + 1;
			if(nex >= N) nex -= N;
			dir[i] = dir[nex] + 1;
			if(r[i] == 1) dir[i] = 0;
		}
	}
		
	return;
}

int compare_plants(int x, int y) {
	if(sub1){
		if(x + dir[x] >= y) return 1;
		if(x - esq[x] < 0 && (x + N - esq[x]) % N <= y) return 1;
		if(y - esq[y] <= x) return -1;
		if(y + dir[y] > N && (y + dir[y]) % N >= x) return -1;
		return 0;
	}
	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