oj.uz

Submission #452063

# Submission time Handle Problem Language Result Execution time Memory
452063 2021-08-03T17:27:53 Z rainboy Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 8644 KB 
#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;
				}
			if (i == n)
				for (i = 0; i < n; i++)
					if (rr[i] == 0)
						break;
			hh[i] = h;
			rr[i] = INF;
			for (i_ = 0; i_ < k; i_++)
				rr[(i - i_ + n) % 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 60 ms 3036 KB Output is correct
7 Correct 70 ms 3252 KB Output is correct
8 Correct 97 ms 4936 KB Output is correct
9 Correct 94 ms 4940 KB Output is correct
10 Correct 95 ms 4952 KB Output is correct
11 Correct 93 ms 4960 KB Output is correct
12 Correct 91 ms 4932 KB Output is correct
13 Correct 87 ms 4932 KB Output is correct
14 Correct 88 ms 5060 KB Output is correct

Subtask #2
14.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 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 10 ms 400 KB Output is correct
7 Correct 248 ms 4980 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 10 ms 332 KB Output is correct
10 Correct 256 ms 4972 KB Output is correct
11 Correct 195 ms 4952 KB Output is correct
12 Correct 190 ms 5204 KB Output is correct
13 Correct 292 ms 5060 KB Output is correct

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 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 10 ms 400 KB Output is correct
7 Correct 248 ms 4980 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 10 ms 332 KB Output is correct
10 Correct 256 ms 4972 KB Output is correct
11 Correct 195 ms 4952 KB Output is correct
12 Correct 190 ms 5204 KB Output is correct
13 Correct 292 ms 5060 KB Output is correct
14 Correct 2147 ms 5476 KB Output is correct
15 Execution timed out 4086 ms 8644 KB Time limit exceeded
16 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 Correct 0 ms 204 KB Output is correct
3 Correct 64 ms 4820 KB Output is correct
4 Execution timed out 4086 ms 7268 KB Time limit exceeded
5 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 Correct 0 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 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 204 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 60 ms 3036 KB Output is correct
7 Correct 70 ms 3252 KB Output is correct
8 Correct 97 ms 4936 KB Output is correct
9 Correct 94 ms 4940 KB Output is correct
10 Correct 95 ms 4952 KB Output is correct
11 Correct 93 ms 4960 KB Output is correct
12 Correct 91 ms 4932 KB Output is correct
13 Correct 87 ms 4932 KB Output is correct
14 Correct 88 ms 5060 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 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 10 ms 400 KB Output is correct
21 Correct 248 ms 4980 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 10 ms 332 KB Output is correct
24 Correct 256 ms 4972 KB Output is correct
25 Correct 195 ms 4952 KB Output is correct
26 Correct 190 ms 5204 KB Output is correct
27 Correct 292 ms 5060 KB Output is correct
28 Correct 2147 ms 5476 KB Output is correct
29 Execution timed out 4086 ms 8644 KB Time limit exceeded
30 Halted 0 ms 0 KB -