oj.uz

Submission #417153

# Submission time Handle Problem Language Result Execution time Memory
417153 2021-06-03T12:14:47 Z KoD Comparing Plants (IOI20_plants) C++17
32 / 100
 987 ms 19452 KB 
#include <bits/stdc++.h>
#include "plants.h"

template <class T> using Vec = std::vector<T>;

constexpr int INF = 1000000000;

struct Monoid {
	int min;
	explicit constexpr Monoid(const int m): min(m) {}
	static constexpr Monoid zero() {
		return Monoid(INF);
	}
	constexpr Monoid operator + (const Monoid& other) const {
		return Monoid(std::min(min, other.min));
	}
};

struct Effector {
	int add;
	explicit constexpr Effector(const int a): add(a) {}
	static constexpr Effector one() {
		return Effector(0);
	}
	constexpr Effector operator * (const Effector& other) const {
		return Effector(add + other.add);
	}
};

constexpr Monoid operator * (const Monoid& m, const Effector& e) {
	return Monoid(m.min + e.add);
}

struct Segtree {
	struct Node {
		Monoid mn;
		Effector ef;
	};

	int size, log;
	Vec<Node> data;

	void fetch(const int k) {
		assert(1 <= k and k < size);
		data[k].mn = data[2 * k].mn + data[2 * k + 1].mn;
	}
	void apply(const int k, const Effector& e) {
		assert(1 <= k and k < 2 * size);
		data[k].mn = data[k].mn * e;
		data[k].ef = data[k].ef * e;
	}
	void flush(const int k) {
		assert(k < size);
		assert(1 <= k);
		apply(2 * k, data[k].ef);
		apply(2 * k + 1, data[k].ef);
		data[k].ef = Effector::one();
	}

	void push(const int k) {
		const int lsb = __builtin_ctz(k);
		const int width = 31 - __builtin_clz(k);
		for (int d = width; d > lsb; --d) {
			flush(k >> d);
		}
	}
	void pull(int k) {
		k >>= __builtin_ctz(k);
		while (k > 1) {
			k >>= 1;
			fetch(k);
		}
	}

	Segtree(const Vec<int>& vec) {
		log = 0;
		while ((1 << log) < (int) vec.size()) {
			log += 1;
		}
		size = 1 << log;
		data.assign(2 * size, Node{Monoid::zero(), Effector::one()});
		for (int i = 0; i < (int) vec.size(); ++i) {
			data[i + size].mn = Monoid(vec[i]);
		}
		for (int i = size - 1; i > 0; --i) {
			fetch(i);
		}
	}

	void add(int l, int r, const int x) {
		l += size;
		r += size;
		push(l);
		push(r);
		const Effector e(x);
		for (int l0 = l, r0 = r; l0 < r0; l0 >>= 1, r0 >>= 1) {
			if (l0 & 1) apply(l0++, e);
			if (r0 & 1) apply(--r0, e);
		}
		pull(l);
		pull(r);
	}

	void enum_zero(Vec<int>& list) {
		auto dfs = [&](auto&& dfs, const int k) {
			if (data[k].mn.min != 0) {
				return;
			}
			if (k < size) {
				flush(k);
				dfs(dfs, 2 * k);
				dfs(dfs, 2 * k + 1);
			}
			else {
				list.push_back(k - size);
			}
		};
		dfs(dfs, 1);
	}

	void assign(int i, const int v) {
		i += size;
		push(i);
		push(i + 1);
		data[i].mn = Monoid(v);
		pull(i);
		pull(i + 1);
	}
};

int Type;
Vec<int> restore;
Vec<Vec<std::pair<int, int>>> belong;

void init(int k, Vec<int> r) {
	const int n = (int) r.size();
	if (k == 2) {
		Type = 1;
		int b = 0;
		belong.resize(n);
		for (int i = 0; i < n; ++i) {
			if (r[i] == 1 and r[(i + n - 1) % n] == 0) {
				int j = i, k = 0;
				while (true) {
					belong[j].emplace_back(b, k);
					std::cerr << j << ' ';
					j -= 1;
					k += 1;
					if (j < 0) {
						j += n;
					}
					if (r[j] == 1) {
						break;
					}
				}
				std::cerr << std::endl;
				b += 1;
				j = i, k = 0;
				while (true) {
					belong[j].emplace_back(b, k);
					std::cerr << j << ' ';
					if (r[j] == 0) {
						break;
					}
					j += 1;
					k += 1;
					if (j >= n) {
						j -= n;
					}
				}
				b += 1;
				std::cerr << std::endl;
			}
		}
	} else if (2 * k > n) {
		Type = 2;
		restore.resize(n);
		Segtree seg(r);
		std::set<int> zero;
		const auto near_l = [&](const int x) {
			auto itr = zero.lower_bound(x);
			return itr == zero.begin() ? *zero.rbegin() : *std::prev(itr);
		};
		const auto near_r = [&](const int x) {
			auto itr = zero.upper_bound(x);
			return itr == zero.end() ? *zero.begin() : *itr;
		};
		int cand = -1;
		const auto dist = [&](const int l, const int r) {
			return l < r ? r - l : r + n - l;
		};
		for (int max = n - 1; max >= 0; --max) {
			Vec<int> add;
			seg.enum_zero(add);
			for (const auto x: add) {
				seg.assign(x, INF);
				zero.insert(x);
			}
			const auto idx = [&] {
				for (const auto x: add) {
					if (dist(near_l(x), x) >= k) {
						return x;
					}
				}
				return cand;				
			}();
			restore[idx] = max;
			if (idx >= k - 1) {
				seg.add(idx - k + 1, idx, -1);
			}
			else {
				seg.add(0, idx, -1);
				seg.add(n - (k - idx - 1), n, -1);
			}
			zero.erase(idx);	
			cand = zero.empty() ? -1 : near_r(idx);
		}
		for (const auto x: restore) {
			std::cerr << x << ' ';
		}
		std::cerr << std::endl;
	}
}

int compare_plants(int x, int y) {
	if (Type == 1) {
		for (const auto [a, b]: belong[x]) {
			for (const auto [c, d]: belong[y]) {
				if (a == c) {
					return b > d ? 1 : -1;
				}
			}
		}
		return 0;
	} else if (Type == 2) {
		return restore[x] > restore[y] ? 1 : -1;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 63 ms 4016 KB Output is correct
7 Correct 135 ms 6580 KB Output is correct
8 Correct 829 ms 19452 KB Output is correct
9 Correct 751 ms 19412 KB Output is correct
10 Correct 742 ms 19296 KB Output is correct
11 Correct 735 ms 19268 KB Output is correct
12 Correct 732 ms 19336 KB Output is correct
13 Correct 737 ms 19252 KB Output is correct
14 Correct 737 ms 19424 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 84 ms 4464 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 80 ms 4492 KB Output is correct
11 Correct 81 ms 4320 KB Output is correct
12 Correct 78 ms 4524 KB Output is correct
13 Correct 84 ms 4436 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 84 ms 4464 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 80 ms 4492 KB Output is correct
11 Correct 81 ms 4320 KB Output is correct
12 Correct 78 ms 4524 KB Output is correct
13 Correct 84 ms 4436 KB Output is correct
14 Correct 144 ms 4576 KB Output is correct
15 Correct 984 ms 11480 KB Output is correct
16 Correct 158 ms 4552 KB Output is correct
17 Correct 969 ms 11504 KB Output is correct
18 Correct 968 ms 16176 KB Output is correct
19 Correct 915 ms 11460 KB Output is correct
20 Correct 987 ms 11544 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 204 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 276 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 63 ms 4016 KB Output is correct
7 Correct 135 ms 6580 KB Output is correct
8 Correct 829 ms 19452 KB Output is correct
9 Correct 751 ms 19412 KB Output is correct
10 Correct 742 ms 19296 KB Output is correct
11 Correct 735 ms 19268 KB Output is correct
12 Correct 732 ms 19336 KB Output is correct
13 Correct 737 ms 19252 KB Output is correct
14 Correct 737 ms 19424 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 6 ms 332 KB Output is correct
21 Correct 84 ms 4464 KB Output is correct
22 Correct 2 ms 308 KB Output is correct
23 Correct 6 ms 332 KB Output is correct
24 Correct 80 ms 4492 KB Output is correct
25 Correct 81 ms 4320 KB Output is correct
26 Correct 78 ms 4524 KB Output is correct
27 Correct 84 ms 4436 KB Output is correct
28 Correct 144 ms 4576 KB Output is correct
29 Correct 984 ms 11480 KB Output is correct
30 Correct 158 ms 4552 KB Output is correct
31 Correct 969 ms 11504 KB Output is correct
32 Correct 968 ms 16176 KB Output is correct
33 Correct 915 ms 11460 KB Output is correct
34 Correct 987 ms 11544 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Incorrect 1 ms 288 KB Output isn't correct
37 Halted 0 ms 0 KB -