Submission #832414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
832414	2023-08-21T10:10:28 Z	Johann	Comparing Plants (IOI20_plants)	C++14	5 / 100	160 ms	30640 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	44 ms	3036 KB	Output is correct
7	Correct	58 ms	5220 KB	Output is correct
8	Correct	132 ms	30640 KB	Output is correct
9	Correct	135 ms	30540 KB	Output is correct
10	Correct	136 ms	30552 KB	Output is correct
11	Correct	135 ms	30540 KB	Output is correct
12	Correct	155 ms	30616 KB	Output is correct
13	Correct	148 ms	30540 KB	Output is correct
14	Correct	160 ms	30528 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Runtime error	1 ms	340 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Runtime error	1 ms	340 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	1 ms	340 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Runtime error	1 ms	340 KB	Execution killed with signal 6
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Runtime error	1 ms	340 KB	Execution killed with signal 6
5	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	44 ms	3036 KB	Output is correct
7	Correct	58 ms	5220 KB	Output is correct
8	Correct	132 ms	30640 KB	Output is correct
9	Correct	135 ms	30540 KB	Output is correct
10	Correct	136 ms	30552 KB	Output is correct
11	Correct	135 ms	30540 KB	Output is correct
12	Correct	155 ms	30616 KB	Output is correct
13	Correct	148 ms	30540 KB	Output is correct
14	Correct	160 ms	30528 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Runtime error	1 ms	340 KB	Execution killed with signal 6
18	Halted	0 ms	0 KB	-