Submission #832414

#	Time	Username	Problem	Language	Result	Execution time	Memory
832414		Johann	Comparing Plants (IOI20_plants)	C++14	5 / 100	160 ms	30640 KiB

plants

#include "plants.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
vvi lift;

void init(int k, std::vector<int> r)
{
	assert(k == 2);
	N = sz(r);
	lift.assign(N, vi(ceil(log2(N) + 1)));
	for (int i = 0; i < N; ++i)
		lift[i][0] = (r[i] == 1) ? 1 : -1;
	for (int j = 1; j < sz(lift[0]); ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			if (lift[i][j - 1] == 0 || lift[i][j - 1] != lift[(i + (1 << (j - 1))) % N][j - 1])
				lift[i][j] = 0;
			else
				lift[i][j] = lift[i][j - 1];
		}
	}

	return;
}

int compare_helper(int x, int y)
{
	assert(x < y);
	int initial = lift[x % N][0];
	for (int j = sz(lift[x % N]); j >= 0; --j)
	{
		int nx = x + (1 << j);
		if (nx > y)
			continue;
		if (lift[x % N][j] != initial)
			return 0;
		x = nx;
	}
	return -1 * initial;
}
int compare_plants(int x, int y)
{
	int factor = 1;
	if (x > y)
		swap(x, y), factor *= -1;
	int tmp = factor * compare_helper(x, y);
	if (tmp != 0)
		return tmp;
	factor *= -1;
	return factor * compare_helper(y, x + N);
}

• 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