oj.uz

Submission #1043253

# Submission time Handle Problem Language Result Execution time Memory
1043253 2024-08-04T06:39:10 Z thinknoexit Comparing Plants (IOI20_plants) C++17
5 / 100
 45 ms 9588 KB 
#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 = 0;
		for (int j = 1;j < sz;j++) {
			if (p[j] - p[j - 1] >= k) idx = j;
		}
		for (int j = 0;j < sz;j++) {
			ord[p[(idx + j) % 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 27 ms 4056 KB Output is correct
7 Correct 31 ms 5720 KB Output is correct
8 Correct 41 ms 9552 KB Output is correct
9 Correct 45 ms 9588 KB Output is correct
10 Correct 40 ms 9296 KB Output is correct
11 Correct 41 ms 8784 KB Output is correct
12 Correct 42 ms 8788 KB Output is correct
13 Correct 40 ms 8788 KB Output is correct
14 Correct 40 ms 8788 KB Output is correct

Subtask #2
0 / 14.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 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 348 KB Output is correct
2 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 1116 KB Output is correct
3 Incorrect 27 ms 5776 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 1 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 1 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 27 ms 4056 KB Output is correct
7 Correct 31 ms 5720 KB Output is correct
8 Correct 41 ms 9552 KB Output is correct
9 Correct 45 ms 9588 KB Output is correct
10 Correct 40 ms 9296 KB Output is correct
11 Correct 41 ms 8784 KB Output is correct
12 Correct 42 ms 8788 KB Output is correct
13 Correct 40 ms 8788 KB Output is correct
14 Correct 40 ms 8788 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 1116 KB Output isn't correct
18 Halted 0 ms 0 KB -