Submission #452061

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
452061	2021-08-03T17:24:51 Z	rainboy	Comparing Plants (IOI20_plants)	C++17	5 / 100	103 ms	5056 KB

plants

#include "plants.h"

using namespace std;

typedef vector<int> vi;

const int N = 200000, INF = 0x3f3f3f3f;

int pp[N], hh[N], n, k;

void init(int k_, vi rr) {
	int h, i;

	n = rr.size(), k = k_;
	if (k == 2) {
		for (i = 0; i < n; i++)
			pp[i] = rr[i];
		for (i = 1; i < n; i++)
			pp[i] += pp[i - 1];
	} else {
		for (h = n - 1; h >= 0; h--) {
			int i_ = -1;

			for (i = 0; i < n; i++)
				if (rr[i] == 0) {
					if (i_ != -1 && i - i_ >= k_)
						break;
					i_ = i;
				}
			i = i_;
			hh[i] = h;
			rr[i] = INF;
			for (i_ = 0; i_ < k; i_++)
				rr[(i + i_) % n]--;
		}
	}
}

int compare_plants(int x, int y) {
	if (k == 2) {
		int c = pp[y - 1] - (x == 0 ? 0 : pp[x - 1]);

		if (c == y - x)
			return -1;
		else if (c == 0)
			return 1;
		c = pp[n - 1] - c;
		if (c == n - (y - x))
			return 1;
		else if (c == 0)
			return -1;
		return 0;
	} else
		return hh[x] < hh[y] ? -1 : 1;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	61 ms	3032 KB	Output is correct
7	Correct	72 ms	3228 KB	Output is correct
8	Correct	95 ms	5056 KB	Output is correct
9	Correct	95 ms	4972 KB	Output is correct
10	Correct	96 ms	4972 KB	Output is correct
11	Correct	96 ms	4956 KB	Output is correct
12	Correct	103 ms	4956 KB	Output is correct
13	Correct	93 ms	4960 KB	Output is correct
14	Correct	89 ms	4960 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Runtime error	1 ms	332 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	204 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	0 ms	328 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	61 ms	3032 KB	Output is correct
7	Correct	72 ms	3228 KB	Output is correct
8	Correct	95 ms	5056 KB	Output is correct
9	Correct	95 ms	4972 KB	Output is correct
10	Correct	96 ms	4972 KB	Output is correct
11	Correct	96 ms	4956 KB	Output is correct
12	Correct	103 ms	4956 KB	Output is correct
13	Correct	93 ms	4960 KB	Output is correct
14	Correct	89 ms	4960 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-