Submission #823247

#	Time	Username	Problem	Language	Result	Execution time	Memory
823247		NothingXD	Comparing Plants (IOI20_plants)	C++17	11 / 100	40 ms	5424 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 300 + 10;
const int inf = 1e6;

int n, k, a[maxn], val[maxn], seg[maxn << 2][2], lazy[maxn << 2][2];
bool mark[maxn], vis[maxn][maxn];
vector<int> g[maxn];

void shift(int v, int x, int l, int r);

void add(int v, int x, int l, int r, int ql, int qr, int val){
	//if (v == 1) debug(ql, qr, val);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
	//	debug(l, r, ql, qr, val);
		seg[v][x] += val;
		lazy[v][x] += val;
		return;
	}
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, ql, qr, val);
	add(v << 1 | 1, x, mid, r, ql, qr, val);
	seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}

int find0(int v, int x, int l, int r){
	if (seg[v][x] != 0) return -1;
	if (l + 1 == r) return l;
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	int res = find0(v << 1, x, l, mid);
	if (res == -1) return find0(v << 1 | 1, x, mid, r);
	return res;
}

void shift(int v, int x, int l, int r){
	if (lazy[v][x] == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, l, mid, lazy[v][x]);
	add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
	lazy[v][x] = 0;
}

void dfs(int v, int r){
	vis[r][v] = true;
	for (auto u: g[v]){
		if (!vis[r][u]) dfs(u, r);
	}
}

void init(int _k, std::vector<int> r) {
	n = r.size();
	k = _k;
	for (int i = 0; i < n; i++){
		a[i] = r[i];
		add(1, 0, 0, n, i, i+1, a[i]);
		add(1, 1, 0, n, i, i+1, a[i]);
	}
	vector<int>topol;
	for (int i = 0; i < n; i++){
		int tmp;
		while((tmp = find0(1, 1, 0, n)) != -1){
			//debug(tmp);
			add(1, 0, 0, n, tmp+1, tmp+k, 1);
			if (tmp+k > n){
				add(1, 0, 0, n, 0, tmp+k-n, 1);
			}
			add(1, 1, 0, n, tmp, tmp+1, inf);
		}
		tmp = find0(1, 0, 0, n);
	//	debug(tmp);
		add(1, 0, 0, n, tmp+1, tmp+k, -1);
		if (tmp+k > n){
			add(1, 0, 0, n, 0, tmp+k-n, -1);
		}
		add(1, 0, 0, n, tmp-k+1, tmp, -1);
		add(1, 1, 0, n, tmp-k+1, tmp, -1);
		if (tmp-k+1 < 0){
			add(1, 0, 0, n, tmp-k+1+n, n, -1);
			add(1, 1, 0, n, tmp-k+1+n, n, -1);
		}
		mark[tmp] = true;
		//debug(tmp);
		for (int i = 1; i < k; i++){
			int u = (tmp+i) % n;
		//	debug(u, mark[u]);
			if (!mark[u]){
			//	debug(1);
				g[tmp].push_back(u);
			}
			u = (tmp-i+n) % n;
		//	debug(u, mark[u]);
			if (!mark[u]){
			//	debug(1);
				g[tmp].push_back(u);
			}
		}
		assert(tmp != -1);
		topol.push_back(tmp);
		val[tmp] = n-i;
		add(1, 0, 0, n, tmp, tmp+1, inf);
	}
	for (int i = 0; i < n; i++){
		dfs(i, i);
	}
	k = _k;
}

int compare_plants(int x, int y) {
	return (vis[x][y]? 1: (vis[y][x]? -1: 0));
}

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