oj.uz

답안 #832474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832474 2023-08-21T10:45:11 Z penguinman 식물 비교 (IOI20_plants) C++17
38 / 100
 558 ms 32972 KB 
#include "plants.h"
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);

template<typename T = pii, typename S = ll>
struct lazy_segment_tree{
	int N, log;
	T valINF;
	S lazyINF;
	vector<T> node;
	vector<S> lazy;
	lazy_segment_tree(int n, T valINF_, S lazyINF_): valINF(valINF_), lazyINF(lazyINF_){
		N = 1;
		log = 1;
		while(N <= n){
			N *= 2;
			log++;
		}
		node.resize(2*N, valINF);
		lazy.resize(2*N, lazyINF);
	}
	void init(vector<T> a){
		rep(i,0,a.size()) node[i+N] = a[i];
		per(i,N-1,1) node[i] = compare(node[i*2], node[i*2+1]);
	}
	void range_add(S val, ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		eval(now);
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			addition(lazy[now], val);
			eval(now);
			return;
		}
		range_add(val, a, b, now*2, l, (l+r)/2);
		range_add(val, a, b, now*2+1, (l+r)/2, r);
		node[now] = compare(node[now*2], node[now*2+1]);
	}
	T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		eval(now);
		if(r <= a || b <= l) return valINF;
		if(a <= l && r <= b) return node[now];
		T L = calc(a, b, now*2, l, (l+r)/2);
		T R = calc(a, b, now*2+1, (l+r)/2, r);
		return compare(L,R);
	}
	void update(ll idx, T val){
		ll now = idx+N;
		per(i,log,0){
			eval(now>>i);
		}
		node[now] = val;
		now /= 2;
		while(now){
			eval(now*2);
			eval(now*2+1);
			node[now] = compare(node[now*2], node[now*2+1]);
			now /= 2;
		}
	}
	void eval(ll now){
		addition(node[now], lazy[now]);
		if(now < N){
			addition(lazy[now*2], lazy[now]);
			addition(lazy[now*2+1], lazy[now]);
		}
		lazy[now] = lazyINF;
	}
	void addition(T &a, S b){
		a.first += b;
	}
	void addition(S &a, S b){
		a += b;
	}
	T compare(T a, T b){
		return std::min(a, b);
	}
};


ll N;
vi height;

void subtask_2_3(int k, vector<int> r){
	N = r.size();
	lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
	{
		vector<pii> a(N);
		rep(i,0,N) a[i] = mp(r[i], i);
		seg.init(a);
	}
	height.resize(N);
	ll now = N;

	std::set<ll> cand;

	std::set<ll> top;

	auto check = [&](ll idx){
		auto itr = cand.lower_bound(idx);
		itr--;
		ll right = idx+k-1;
		right -= N;
		if(*itr <= right) return true;
		else return false;
	};

	while(true){
		while(true){
			auto el = seg.calc(0,N);
			if(el.first) break;
			ll i = el.second;
			cand.insert(i);
			cand.insert(i-N);
			cand.insert(i+N);
			if(check(i)) top.insert(i);
			if(cand.size() > 3){
				ll upper = *cand.upper_bound(i);
				if(upper >= N) upper -= N;
				if(top.count(upper)){
					if(!check(upper)) top.erase(upper);
				}
			}
			seg.update(i,mp(inf, 0));
		}
		if(cand.empty()) break;
		assert(top.size() == 1);
		ll t = *top.begin();
		height[t] = now--;
		{
			ll l = t-k+1;
			ll r = t;
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
		}
		cand.erase(t);
		cand.erase(t-N);
		cand.erase(t+N);
		top.erase(t);
		if(cand.empty()) continue;
		ll upper = *cand.upper_bound(t);
		if(upper >= N) upper -= N;
		if(check(upper)) top.insert(upper);
	}

	/*while((seg.calc(0,N)).first == 0){
		vi idx;
		while(true){
			auto el = seg.calc(0,N);
			if(el.first) break;
			idx.pb(el.second);
			seg.update(el.second, mp(inf, 0));
		}
		if(idx.size() == 1){
			height[idx[0]] = now--;
			ll l = idx[0]-k+1;
			ll r = idx[0];
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
			continue;
		}
		assert(idx.size() == 2);
		if(idx[0] > idx[1]) std::swap(idx[0], idx[1]);
		if(idx[1] < idx[0]+k){
			idx[0] = now--;
			idx[1] = now--;
		}
		else{
			idx[1] = now--;
			idx[0] = now--;
		}
		rep(i,0,2){
			ll l = idx[i]-k+1;
			ll r = idx[i];
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
		}
	}*/
	/*rep(i,0,N) cout << height[i] << " ";
	cout << ln;*/
}

vii edge;

void subtask_5(int k, std::vector<int> r){
	N = r.size();
	edge.resize(N,vi(N));
	vector<bool> flag(N);
	rep(_,0,N){
		ll top = -1;
		rep(i,0,N){
			if(r[i]) continue;
			ll now = i;
			bool f = true;
			rep(j,1,k){
				now--;
				if(now < 0) now += N;
				if(r[now]) continue;
				f = false;
			}
			if(f) top = i;
		}
		flag[top] = true;
		/*cout << top << ln;
		rep(i,0,N) cout << r[i] << " ";
		cout << ln;*/
		ll now = top;
		rep(j,1,k){
			now++;
			now %= N;
			if(flag[now]) continue;
			edge[top][now] = true;
		}
		now = top;
		rep(j,1,k){
			now--;
			if(now < 0) now += N;
			r[now]--;
			if(flag[now]) continue;
			edge[top][now] = true;
		}
		r[top] = 1e9;
	}
	rep(k,0,N){
		rep(i,0,N){
			rep(j,0,N){
				edge[i][j] |= (edge[i][k]&edge[k][j]);
			}
		}
	}
}

vii par;
vector<int> r_mem;

void subtask_1(int k, std::vector<int> r){
	N = r.size();
	par.resize(N);
	rep(i,0,N){
		if(r[i] == 0){
			par[(i+1)%N].pb(i);
		}
		else{
			par[i].pb((i+1)%N);
		}
	}
	r_mem = r;
}

vi answer;
bool is_6 = false;

void subtask_4_6(int k, vector<int> r){
	is_6 = true;
	answer.resize(N);
	{
		auto rrr = r;
		N = r.size();
		lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
		{
			vector<pii> a(N);
			rep(i,0,N) a[i] = mp(r[i], i);
			seg.init(a);
		}
		height.resize(N);
		ll now = N;

		std::set<ll> cand;

		std::set<ll> top;

		auto check = [&](ll idx){
			auto itr = cand.lower_bound(idx);
			itr--;
			if(idx-*itr <= k-1) return false;
			else return true;
		};

		vi ord;

		while(true){
			while(true){
				auto el = seg.calc(0,N);
				if(el.first) break;
				ll i = el.second;
				cand.insert(i);
				cand.insert(i-N);
				cand.insert(i+N);
				if(check(i)) top.insert(i);
				if(cand.size() > 3){
					ll upper = *cand.upper_bound(i);
					if(upper >= N) upper -= N;
					if(top.count(upper)){
						if(!check(upper)) top.erase(upper);
					}
				}
				seg.update(i,mp(inf, 0));
			}
			if(cand.empty()) break;
			ll t = *top.begin();
			height[t] = now--;
			ord.pb(t);
			{
				ll l = t-k+1;
				ll r = t;
				if(0 <= l) seg.range_add(-1, l, r);
				else{
					seg.range_add(-1, 0, r);
					seg.range_add(-1, N+l, N);
				}
			}
			cand.erase(t);
			cand.erase(t-N);
			cand.erase(t+N);
			top.erase(t);
			if(cand.empty()) continue;
			ll upper = *cand.upper_bound(t);
			if(upper >= N) upper -= N;
			if(check(upper)) top.insert(upper);
		}
		r = rrr;

		std::set<ll> remain;
		rep(i,0,N) remain.insert(i), remain.insert(i+N), remain.insert(i-N);
		vector<bool> flag(N);
		flag[0] = true;
		for(auto i: ord){
			if(remain.count(i)){
				remain.erase(i);
				remain.erase(i+N);
				remain.erase(i-N);
			}
			if(!flag[i]) continue;
			while(true){
				auto itr = remain.upper_bound(i);
				if(itr == remain.end()) break;
				if(*itr-i > k-1) break;
				ll now = *itr;
				now %= N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
			while(true){
				auto itr = remain.lower_bound(i);
				if(itr == remain.begin()) break;
				itr--;
				if(i-*itr > k-1) break;
				ll now = *itr;
				now %= N;
				if(now < 0) now += N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
		}
		rep(i,0,N){
			if(flag[i]) answer[i] = 1;
		}
	}

	{
		auto rrr = r;
		rep(i,0,N) r[i] = k-1-r[i];
		lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
		{
			vector<pii> a(N);
			rep(i,0,N) a[i] = mp(r[i], i);
			seg.init(a);
		}
		height.resize(N);
		ll now = N;

		std::set<ll> cand;

		std::set<ll> top;

		auto check = [&](ll idx){
			auto itr = cand.lower_bound(idx);
			itr--;
			if(idx-*itr <= k-1) return false;
			else return true;
		};

		vi ord;

		while(true){
			while(true){
				auto el = seg.calc(0,N);
				if(el.first) break;
				ll i = el.second;
				cand.insert(i);
				cand.insert(i-N);
				cand.insert(i+N);
				if(check(i)) top.insert(i);
				if(cand.size() > 3){
					ll upper = *cand.upper_bound(i);
					if(upper >= N) upper -= N;
					if(top.count(upper)){
						if(!check(upper)) top.erase(upper);
					}
				}
				seg.update(i,mp(inf, 0));
			}
			if(cand.empty()) break;
			ll t = *top.begin();
			height[t] = now--;
			ord.pb(t);
			{
				ll l = t-k+1;
				ll r = t;
				if(0 <= l) seg.range_add(-1, l, r);
				else{
					seg.range_add(-1, 0, r);
					seg.range_add(-1, N+l, N);
				}
			}
			cand.erase(t);
			cand.erase(t-N);
			cand.erase(t+N);
			top.erase(t);
			if(cand.empty()) continue;
			ll upper = *cand.upper_bound(t);
			if(upper >= N) upper -= N;
			if(check(upper)) top.insert(upper);
		}
		r = rrr;

		std::set<ll> remain;
		rep(i,0,N) remain.insert(i), remain.insert(i+N), remain.insert(i-N);
		vector<bool> flag(N);
		flag[0] = true;
		for(auto i: ord){
			if(remain.count(i)){
				remain.erase(i);
				remain.erase(i+N);
				remain.erase(i-N);
			}
			if(!flag[i]) continue;
			while(true){
				auto itr = remain.upper_bound(i);
				if(itr == remain.end()) break;
				if(*itr-i > k-1) break;
				ll now = *itr;
				now %= N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
			while(true){
				auto itr = remain.lower_bound(i);
				if(itr == remain.begin()) break;
				itr--;
				if(i-*itr > k-1) break;
				ll now = *itr;
				now %= N;
				if(now < 0) now += N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
		}
		rep(i,0,N){
			if(flag[i]) answer[i] = -1;
		}
	}

	{
		auto rrr = r;
		rep(i,0,N) r[i] = k-1-r[i];
		lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
		{
			vector<pii> a(N);
			rep(i,0,N) a[i] = mp(r[i], i);
			seg.init(a);
		}
		ll now = N;

		std::set<ll> cand;

		std::set<ll> top;

		auto check = [&](ll idx){
			auto itr = cand.lower_bound(idx);
			itr--;
			if(idx-*itr <= k-1) return false;
			else return true;
		};

		vi ord;

		while(true){
			while(true){
				auto el = seg.calc(0,N);
				if(el.first) break;
				ll i = el.second;
				cand.insert(i);
				cand.insert(i-N);
				cand.insert(i+N);
				if(check(i)) top.insert(i);
				if(cand.size() > 3){
					ll upper = *cand.upper_bound(i);
					if(upper >= N) upper -= N;
					if(top.count(upper)){
						if(!check(upper)) top.erase(upper);
					}
				}
				seg.update(i,mp(inf, 0));
			}
			if(cand.empty()) break;
			ll t = *top.begin();
			height[t] = now--;
			ord.pb(t);
			{
				ll l = t-k+1;
				ll r = t;
				if(0 <= l) seg.range_add(-1, l, r);
				else{
					seg.range_add(-1, 0, r);
					seg.range_add(-1, N+l, N);
				}
			}
			cand.erase(t);
			cand.erase(t-N);
			cand.erase(t+N);
			top.erase(t);
			if(cand.empty()) continue;
			ll upper = *cand.upper_bound(t);
			if(upper >= N) upper -= N;
			if(check(upper)) top.insert(upper);
		}
		r = rrr;
	}
}

void init(int k, std::vector<int> r) {
	N = r.size();
	if(N <= 300) subtask_5(k,r);
	else if(2*k > N) subtask_2_3(k,r);
	else subtask_4_6(k,r);
}

int compare_plants(int x, int y) {
	if(!height.empty()){
		if(x == 0 && is_6 && answer[y]) return answer[y];
		if(height[x] < height[y]) return -1;
		else return 1;
	}
	else if(!edge.empty()){
		if(edge[x][y]) return 1;
		else if(edge[y][x]) return -1;
		else return 0;
	}
	else{
		std::function<ll(ll)> root = [&](ll now){
			if(par[now].empty()) return now;
			return par[now][0] = root(par[now][0]);	
		};
		if(par[x].size() == 2 && par[y].size() == 2) return 0;
		if(par[x].empty() && par[y].empty()) return 0;
		if(par[x].size() == 2){
			if(root(par[x][0]) == root(y)) return -1;
			if(root(par[x][1]) == root(y)) return -1;
			return 0;
		}
		if(par[y].size() == 2){
			if(root(par[y][0]) == root(x)) return 1;
			if(root(par[y][1]) == root(x)) return 1;
			return 0;
		}
		if(root(x) != root(y)) return 0;
		if(r_mem[x] == 0 && r_mem[(y+N-1)%N] == 0) return 1;
		if(r_mem[y] == 0 && r_mem[(x+N-1)%N] == 0) return -1;
		if(r_mem[x] == 1 && r_mem[(y+1)%N] == 1) return -1;
		if(r_mem[y] == 1 && r_mem[(x+1)%N] == 1) return 1;
	}
}

Compilation message

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:611:1: warning: control reaches end of non-void function [-Wreturn-type]
  611 | }
      | ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 49 ms 3024 KB Output is correct
7 Incorrect 153 ms 8268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 49 ms 3368 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 52 ms 3536 KB Output is correct
11 Correct 44 ms 3536 KB Output is correct
12 Correct 42 ms 3512 KB Output is correct
13 Correct 47 ms 3348 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 49 ms 3368 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 52 ms 3536 KB Output is correct
11 Correct 44 ms 3536 KB Output is correct
12 Correct 42 ms 3512 KB Output is correct
13 Correct 47 ms 3348 KB Output is correct
14 Correct 85 ms 5040 KB Output is correct
15 Correct 446 ms 23540 KB Output is correct
16 Correct 85 ms 4940 KB Output is correct
17 Correct 423 ms 23508 KB Output is correct
18 Correct 558 ms 32972 KB Output is correct
19 Correct 296 ms 23504 KB Output is correct
20 Correct 388 ms 23500 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 45 ms 3608 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 28 ms 1552 KB Output is correct
8 Correct 32 ms 1620 KB Output is correct
9 Correct 28 ms 1612 KB Output is correct
10 Correct 29 ms 1544 KB Output is correct
11 Correct 28 ms 1544 KB Output is correct
12 Correct 28 ms 1600 KB Output is correct
13 Correct 29 ms 1580 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 5 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 49 ms 3024 KB Output is correct
7 Incorrect 153 ms 8268 KB Output isn't correct
8 Halted 0 ms 0 KB -