Submission #1213025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213025		thelegendary08	Comparing Plants (IOI20_plants)	C++17	19 / 100	4093 ms	6684 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vb vector<bool>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<'\n';
using namespace std;
int n;
vi v;
int k;
vi ps;
int sum(int l, int r){
	// dout2(l,r);
	int thing, len;
	if(l <= r){
		thing = ps[r+1] - ps[l];
		len = r - l + 1;
	}
	else{
		//sum from r + 1 to l - 1
		thing = ps[n] - (ps[l] - ps[r+1]);
		len = n - (l - r - 1);
	}
	// dout2(thing,len);
	if(thing == len)return 1;
	if(thing == 0)return 0;
	return -1;
}
vi ans;
void init(int k, std::vector<int> r) {
	v = r;
	n = r.size();
	::k=k;
	if(k == 2){
		ps.resize(n+1);
		FOR(i, 1, n+1){
			ps[i] = ps[i-1] + r[i-1];
		}
	}
	else{
		k--;
		ans.resize(n);
		f0r(i,n){
			vi zp;
			f0r(j, n){
				if(r[j] == 0)zp.pb(j);
			}
			int nxt = -1;
			if(zp.size() == 1)nxt = zp[0];
			else{
				f0r(j, zp.size()){
					int prev = (j == 0) ? zp.back() : zp[j-1];
					int dist = (j == 0) ? zp[0] + n - prev : zp[j] - prev;
					// dout2(prev,dist);
					if(dist > k)nxt = zp[j];
				}
			}
			// dout(nxt);
			if(nxt != -1){
				r[nxt] = -1;
				ans[nxt] = n - i;
				for(int j = nxt-1; j >= nxt - k; j--){
					int x = j;
					if(x < 0)x += n;
					r[x]--;
				}
			}
			// vout(r);
			
		}
		// vout(ans);
	}
	
}

int compare_plants(int x, int y) {
	//path from x to y is all 1, means y is taller, return -1
	if(k == 2){
		int rhs = (x == 0) ? n-1 : x-1;
		if(sum(x, y-1) == 1){
			return -1;
		}
		else if(sum(x, y-1) == 0){
			return 1;
		}
		else if(sum(y, rhs) == 1){
			return 1;
		}
		else if(sum(y, rhs) == 0){
			return -1;
		}
		else return 0;
	}
	else{
		if(ans[x] > ans[y])return 1;
		else 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