oj.uz

답안 #832460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832460 2023-08-21T10:37:27 Z penguinman 식물 비교 (IOI20_plants) C++17
11 / 100
 82 ms 7816 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;

void subtask_4_6(int k, vector<int> r){
	N = r.size();
	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);
	}

	answer.resize(N);
	{
		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;
		}
	}
	{
		reverse(all(ord));
		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;
		}
	}
}

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) 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:475:1: warning: control reaches end of non-void function [-Wreturn-type]
  475 | }
      | ^

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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 38 ms 3028 KB Output is correct
7 Incorrect 82 ms 7816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Correct 1 ms 340 KB Output is correct
6 Runtime error 2 ms 620 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Correct 1 ms 340 KB Output is correct
6 Runtime error 2 ms 620 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 43 ms 3520 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 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 29 ms 1568 KB Output is correct
8 Correct 29 ms 1548 KB Output is correct
9 Correct 29 ms 1560 KB Output is correct
10 Correct 29 ms 1612 KB Output is correct
11 Correct 29 ms 1544 KB Output is correct
12 Correct 29 ms 1536 KB Output is correct
13 Correct 29 ms 1552 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 3 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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 38 ms 3028 KB Output is correct
7 Incorrect 82 ms 7816 KB Output isn't correct
8 Halted 0 ms 0 KB -