Submission #1156961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156961		12345678	Comparing Plants (IOI20_plants)	C++20	5 / 100	49 ms	12868 KiB

plants

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

using namespace std;

const int nx=2e5+5;

int N, dpl[nx], dpr[nx];
vector<int> h;

int solvel(int x)
{
	if (dpl[x]!=-1) return dpl[x];
	int prev=(x-1+N)%N;
	if (h[prev]==1) return dpl[x]=solvel(prev);
	return dpl[x]=x;
}

int solver(int x)
{
	if (dpr[x]!=-1) return dpr[x];
	int nxt=(x+1)%N;
	if (h[x]==0) return dpr[x]=solver(nxt);
	return dpr[x]=x;
}

void init(int k, std::vector<int> r) {
	N=r.size();
	h=r;
	for (int i=0; i<N; i++) dpl[i]=dpr[i]=-1;
	for (int i=0; i<N; i++)
	{
		if (dpl[i]==-1) solvel(i);
		if (dpr[i]==-1) solver(i);
		//cout<<i<<' '<<dpl[i]<<' '<<dpr[i]<<'\n';
	}
}

int isgreater(int x, int y)
{
	if (dpl[x]==dpr[x]&&dpl[x]!=x) return 1;
	if (dpl[x]>dpr[x]) 
	{
		if (y>=dpl[x]) return 1;
		if (y<=dpr[x]) return 1;
		return 0;
	}
	return (dpl[x]<=y&&y<=dpr[x]);
}

int compare_plants(int x, int y) {
	if (isgreater(x, y)) return 1;
	if (isgreater(y, x)) 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