Submission #1167422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167422		gyg	Comparing Plants (IOI20_plants)	C++20	14 / 100	4094 ms	6688 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);
	// for (int i = 1; i <= n; i++) cout << sm[i] << " ";
	// cout << '\n';	
}

arr<int, N> vl;
void vl_cmp() {
	for (int x = n; x >= 1; x--) {
		sm_cmp();

		int id = -1;
		// cout << x << ": " << '\n';
		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;
			// cout << y << " ";
		}
		// cout << '\n';
		assert(id != -1);

		vl[id] = x;
		
		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];

	vl_cmp();

	// for (int i = 1; i <= n; i++) cout << vl[i] << " ";
	// cout << '\n';
}

// 0 indexed
int compare_plants(int i, int j) {
	i++, j++;
	return (vl[i] < vl[j]) ? -1 : 1;
}

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