Submission #1169240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169240		gyg	Comparing Plants (IOI20_plants)	C++20	0 / 100	4094 ms	8160 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 2e5 + 5, INF = 1e9;

int n, k;
arr<int, N> a;

int md(int i) { return ((i + n) % n == 0) ? n : (i + n) % n; }
arr<int, N> sm;
int qry_rng(int l, int r) {
	if (l > r) return 0;
	return sm[r] - sm[l - 1];
}
int qry(int i, int j) {
	if (i <= j) return qry_rng(i, j);
	return qry_rng(i, n) + qry_rng(1, j);
}
void sm_cmp() {
	for (int i = 1; i <= n; i++) 
		sm[i] = sm[i - 1] + (a[i] == 0);
}

arr<bool, N> dn;
arr<vec<int>, N> adj;
void adj_cmp() {
	for (int x = n; x >= 1; x--) {
		sm_cmp();

		int id = -1;
		for (int i = 1; i <= n; i++) {
			int y = (a[i] != 0) + qry(md(i - k + 1), md(i - 1));
			if (y == 0) id = i;
		}
		assert(id != -1);
		dn[id] = true;

		for (int i = md(id - k + 1); i != md(id + k); i = md(i + 1))
			if (!dn[i]) adj[id].push_back(i);

		a[id] = INF;
		for (int i = md(id - k + 1); i != id; i = md(i + 1))
			a[i]--;
	}	
}

void init(int _k, vec<int> _a) {
	n = _a.size(), k = _k;
	for (int i = 1; i <= n; i++) a[i] = _a[i - 1];

	adj_cmp();

	// for (int u = 1; u <= n; u++) {
	// 	cout << u << ": ";
	// 	for (int v : adj[u]) cout << v << " ";
	// 	cout << '\n';
	// }
}

arr<bool, N> vs;
void dfs(int u) {
	vs[u] = true;
	for (int v : adj[u])
		if (!vs[v]) dfs(v);
}
bool rch(int u, int v) {
	vs.fill(false);
	dfs(u);
	return vs[v];
}
// 0 indexed
int compare_plants(int i, int j) {
	i++, j++;
	if (rch(i, j)) return 1;
	else if (rch(j, i)) return -1;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25