Submission #1043260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043260	2024-08-04T06:47:51 Z	thinknoexit	Comparing Plants (IOI20_plants)	C++17	5 / 100	49 ms	9044 KB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n, k;
int ord[N], deg[N], dpl[N], dpr[N];
void init(int K, vector<int> r) {
	n = r.size();
	k = K;
	if (k == 2) {
		for (int i = 0;i < n;i++) {
			if (r[i] == 1) deg[(i + 1) % n]++;
			else deg[i]++;
		}
		for (int i = 0;i < n;i++) {
			if (deg[i] != 0) continue;
			dpl[i] = dpr[i] = 0;
			for (int j = 1;j < n;j++) {
				dpr[(i - j + n) % n] = j;
				if (deg[(i - j + n) % n] == 2) break;
			}
			for (int j = 1;j < n;j++) {
				dpl[(i + j) % n] = j;
				if (deg[(i + j) % n] == 2) break;
			}
		}
		return;
	}
	vector<vector<int>> pos(k);
	for (int i = 0;i < n;i++) pos[r[i]].push_back(i);
	memset(ord, -1, sizeof ord);
	int tot = 0;
	for (int i = k - 1;i >= 0;i--) {
		auto p = pos[i];
		int sz = p.size();
		int idx = sz - 1;
		for (int j = 0;j < sz - 1;j++) {
			if (p[j + 1] - p[j] >= k) idx = j;
		}
		for (int j = 0;j < sz;j++) {
			ord[p[(idx - j + sz) % sz]] = ++tot;
		}
	}
}
bool can(int x, int y) {
	int l = dpr[x], r = dpl[x];
	if (x + l >= n) {
		if (x <= y || y <= x + l - n) return 1;
	}
	else {
		if (x <= y && y <= x + l) return 1;
	}
	if (x - r < 0) {
		if (y <= x || n + x - r <= y) return 1;
	}
	else {
		if (x - r <= y && y <= x) return 1;
	}
	return 0;
}
int compare_plants(int x, int y) {
	if (k != 2) return (ord[x] > ord[y]) ? 1 : -1;
	if (can(x, y)) return 1;
	if (can(y, x)) return -1;
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	432 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	25 ms	4184 KB	Output is correct
7	Correct	31 ms	5448 KB	Output is correct
8	Correct	40 ms	9044 KB	Output is correct
9	Correct	41 ms	9040 KB	Output is correct
10	Correct	41 ms	8808 KB	Output is correct
11	Correct	49 ms	8532 KB	Output is correct
12	Correct	42 ms	8272 KB	Output is correct
13	Correct	39 ms	8464 KB	Output is correct
14	Correct	39 ms	8408 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Incorrect	0 ms	1116 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	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	0 ms	1116 KB	Output is correct
4	Incorrect	0 ms	1116 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	348 KB	Output is correct
2	Correct	0 ms	1116 KB	Output is correct
3	Incorrect	28 ms	5452 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Incorrect	0 ms	1116 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	1 ms	1116 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	348 KB	Output is correct
2	Correct	0 ms	432 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	25 ms	4184 KB	Output is correct
7	Correct	31 ms	5448 KB	Output is correct
8	Correct	40 ms	9044 KB	Output is correct
9	Correct	41 ms	9040 KB	Output is correct
10	Correct	41 ms	8808 KB	Output is correct
11	Correct	49 ms	8532 KB	Output is correct
12	Correct	42 ms	8272 KB	Output is correct
13	Correct	39 ms	8464 KB	Output is correct
14	Correct	39 ms	8408 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	0 ms	600 KB	Output is correct
17	Correct	0 ms	1116 KB	Output is correct
18	Incorrect	0 ms	1116 KB	Output isn't correct
19	Halted	0 ms	0 KB	-