Submission #1320658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320658		dibamboo23	Comparing Plants (IOI20_plants)	C++20	5 / 100	45 ms	8956 KiB

plants

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

#define ll long long
#define sz size()
#define F first 
#define S second 

using namespace std;

const int N=1e6+3;

int n;
int r[N];
int p[N];
int s[N];
int p0[N];
int val[N];

bool sub1=0;

void init(int k, vector<int>inr){
	n=(int)inr.sz;
	for(int i=0;i<n;i++)r[i]=r[i+n]=inr[i];
	if(k==2){
		sub1=1;
		int cnt=0;
		for(int i=0;i<n*2;i++){
			cnt++;
			if(r[i]==0)cnt=0;
			p[i]=cnt;
		}
		cnt=0;
		for(int i=n*2-1;i>=0;i--){
			cnt++;
			if(r[i]==1)cnt=0;
			s[i]=cnt;
		}
		return;
	}
	for(int id=n;id>=1;id--){
		for(int i=0;i<n;i++){
			if(r[i]!=0)continue;
			bool t=1;
			int pre=i;
			for(int j=0;j<k-1;j++){
				pre=(pre-1+n)%n;
				if(r[pre]==0){
					t=0;
					break;
				}
			}
			if(t){
				val[i]=id;
				pre=i;
				for(int j=0;j<k-1;j++){
					pre=(pre-1+n)%n;
					r[pre]--;
				}
				break;
			}
		}
	}
	// for(int i=0;i<n;i++)cout<<val[i]<<" ";
	// cout<<"\n";
}

// 0 -  > 
// 1 -  <

int compare_plants(int x, int y) {
	if(sub1){
		int res=0;
		if(x+s[x]>=y||x+n-p[x+n-1]<=y)res=1;
		else if(y-p[n+y-1]<=x||y+s[y]>=x+n)res=-1;
		return res;
	}
	if(val[x]>val[y])return 1;
	else if(val[x]<val[y])return 0;
	else 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