Submission #1018333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018333		Boas	Comparing Plants (IOI20_plants)	C++17	5 / 100	80 ms	7504 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define loop(x, i) for (int i = 0; i < (x); i++)
#define ALL(x) (x).begin(), x.end()
#define pb push_back

vii increasingSegs;
vii decreasingSegs;
int N;
int beg = 0;

void init(int k, vi r)
{
	if (k != 2)
		throw;
	N = r.size();
	for (int i = 0; i < N; i++)
	{
		if (r[i] != r[(i - 1 + N) % N])
		{
			beg = i;
			break;
		}
	}
	int start = 0;
	int prev = r[start + beg];
	for (int i = 1; i <= N; i++)
	{
		int p = (i + beg) % N;
		if (r[p] != prev)
		{
			if (prev == 1)
			{
				increasingSegs.pb({start, i});
			}
			else
			{
				decreasingSegs.pb({start, i});
			}
			start = i;
		}
		prev = r[p];
	}
	return;
}

int compare_plants(int x, int y)
{
	int a = (x - beg + N) % N, b = (y - beg + N) % N;
	auto it = lower_bound(ALL(increasingSegs), ii{min(a, b) + 1, -1});
	auto it2 = lower_bound(ALL(decreasingSegs), ii{min(a, b) + 1, -1});
	if (it != increasingSegs.begin())
	{
		it = prev(it);
		if (it->first <= a && a <= it->second)
		{
			if (it->first <= b && b <= it->second)
			{
				if (b > a)
					return -1;
				return 1;
			}
		}
	}
	if (it2 != decreasingSegs.begin())
	{
		it2 = prev(it2);
		if (it2->first <= a && a <= it2->second)
		{
			if (it2->first <= b && b <= it2->second)
			{
				if (b > a)
					return 1;
				return -1;
			}
		}
	}
	if (a == 0 || b == 0)
	{
		int other = max(a, b);
		if (increasingSegs.back().second == N && increasingSegs.back().first <= other)
		{
			if (a == 0)
				return 1;
			return -1;
		}
		if (decreasingSegs.back().second == N && decreasingSegs.back().first <= other)
		{
			if (a == 0)
				return -1;
			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