Submission #303109

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

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	if (k == 2)
	{
		k0 = k1 = vector<int>(n, 0);
		for (int t = 0; t < 2; t++)
			for (int i = n - 1; i >= 0; i--)
			{
				if (r[i] == 0)
					k0[i] = 1 + k0[(i + 1) % n];
				else
					k1[i] = 1 + k1[(i + 1) % n];
			}
	}
	if (2 * k > n)
	{
		A = vector<int>(n, -1);
		for (int tt = 0; tt < n; tt++)
		{
			for (int i = 0; i < n; i++)
			{
				if (r[i] == 0)
				{
					int j = i;
					bool ok = true;
					for (int t = 0; t < k - 1; t++)
					{
						j--;
						if (j < 0)
							j += n;
						if (r[j] == 0)
						{
							ok = false;
							break;
						}
					}
					if (!ok)
						continue;
					A[i] = tt;
					r[i] = n + 100;
					j = i;
					for (int t = 0; t < k - 1; t++)
					{
						j--;
						if (j < 0)
							j += n;
						r[j]--;
					}
				}
			}
		}
	}
}

int compare_plants(int x, int y)
{
	assert(x < y);
	if (K == 2)
	{
		if (k0[x] >= y - x)
			return 1;
		if (k1[x] >= y - x)
			return -1;
		if (k0[y] >= n - y + x)
			return -1;
		if (k1[y] >= n - y + x)
			return 1;
		return 0;
	}
	if (!A.empty())
	{
		if (A[x] < A[y])
			return -1;
		else
			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