Submission #1043223

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043223	2024-08-04T05:04:46 Z	thinknoexit	Comparing Plants (IOI20_plants)	C++17	5 / 100	52 ms	6492 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;
	}
	memset(ord, -1, sizeof ord);
	for (int i = n;i >= 1;i--) {
		vector<int> v;
		for (int j = 0;j < n;j++) {
			if (ord[j] == -1 && r[j] == 0) {
				v.push_back(j);
			}
		}
		int sz = v.size();
		int idx = 0;
		for (int j = 0;j < sz;j++) {
			if ((v[j] - v[(j + sz - 1) % sz] + n) % n >= k) idx = v[j];
		}
		ord[idx] = i;
		for (int j = 1;j < k;j++) {
			r[(idx - j + n) % n]--;
		}
	}
}
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	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	27 ms	5108 KB	Output is correct
7	Correct	34 ms	5444 KB	Output is correct
8	Correct	39 ms	6492 KB	Output is correct
9	Correct	38 ms	6492 KB	Output is correct
10	Correct	41 ms	6492 KB	Output is correct
11	Correct	40 ms	6480 KB	Output is correct
12	Correct	38 ms	6372 KB	Output is correct
13	Correct	38 ms	6484 KB	Output is correct
14	Correct	52 ms	6484 KB	Output is correct

Subtask #2

0 / 14.0

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

Subtask #3

0 / 13.0

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

Subtask #4

0 / 17.0

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

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Incorrect	0 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	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	27 ms	5108 KB	Output is correct
7	Correct	34 ms	5444 KB	Output is correct
8	Correct	39 ms	6492 KB	Output is correct
9	Correct	38 ms	6492 KB	Output is correct
10	Correct	41 ms	6492 KB	Output is correct
11	Correct	40 ms	6480 KB	Output is correct
12	Correct	38 ms	6372 KB	Output is correct
13	Correct	38 ms	6484 KB	Output is correct
14	Correct	52 ms	6484 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	0 ms	2396 KB	Output is correct
17	Incorrect	0 ms	1116 KB	Output isn't correct
18	Halted	0 ms	0 KB	-