oj.uz

Submission #300628

# Submission time Handle Problem Language Result Execution time Memory
300628 2020-09-17T10:38:06 Z user202729 Comparing Plants (IOI20_plants) C++17
5 / 100
 661 ms 35652 KB 
// moreflags=grader.cpp


#include "plants.h"
#include<vector>
#include<set>
#include<array>
#include<algorithm>
#include<iostream>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>

struct Tree{
	struct Node{
		int lazy, minimum_;
		int minimum() const{return lazy+minimum_;}
	};
	std::vector<Node> data;
	Tree(int number): data(number*2){}
	int offset() const{return int(data.size()/2);}
	void mergeAll(int node){
		assert(node>=offset());
		for(node>>=1; node; node>>=1)
			data[node].minimum_=std::min(data[node*2].minimum(), data[node*2+1].minimum());
	}
	void add(int left, int right, int delta){
		if(left==right) return;
		assert(left<right);

		left+=offset(); right+=offset();
		std::array<int, 2> old{{left, right-1}};
		while(left<right){
			if(left&1) data[left++].lazy+=delta;
			if(right&1) data[--right].lazy+=delta;
			left>>=1; right>>=1;
		}
		for(auto it: old) mergeAll(it);
	}
	void push(int node){
		if(auto const l=data[node].lazy){
			data[node].lazy=0;
			data[node].minimum_+=l;
			data[node*2].lazy+=l;
			data[node*2+1].lazy+=l;
		}
	}
	void pushAll(int node){
		assert(node>=offset());
		for(int shift=31^__builtin_clz(node); shift>0; shift--)
			push(node>>shift);
	}
	int anyZeroNode(int node){
		while(node<offset()){
			push(node);
			node*=2;
			if(data[node].minimum()!=0) ++node;
		}
		assert(data[node].minimum()==0);
		assert((pushAll(node), data[node].minimum()==0));
		return node-offset();
	}
	int anyZero(int left, int right){
		// -1 if not found
		if(left==right) return -1;
		assert(left<right);

		left+=offset(); right+=offset();
		pushAll(left); pushAll(right-1);
#define P(node_) { int node=node_; assert(data[node].minimum()>=0); if(data[node].minimum()==0) return anyZeroNode(node); }
		while(left<right){
			if(left&1) P(left++);
			if(right&1) P(--right);
			left>>=1; right>>=1;
		}
#undef P
		return -1;
	}
};

std::vector<int> permutation, permutationReversed;
int k;
std::vector<std::vector<int>> nextGreaterRight, nextGreaterLeft;
std::vector<std::vector<int>> jumpTable(std::vector<int> data){
	// -1=terminal
	std::vector<std::vector<int>> result{std::move(data)};
	while(true){
		std::vector<int> next=result.back();
		bool useful=false;
		for(auto& it: next) if(it>=0){
			it=result.back()[it];
			useful=useful or it>=0;
		}
		if(useful) result.push_back(std::move(next)); else break;
	}
	return result;
}

// for each index i, compute the index in (i+1..i+k) mod data.size()
// with minimum data value and greater than current data
// or -1 if not found
std::vector<int> nextGreater(int k, std::vector<int> const& data){
	std::set<int> remaining;
	int const number=(int)data.size();
	std::vector<int> result(number, -1);
	std::vector<int> indexOf(number, -1);
	for(int index=0; index<number; ++index){
		assert(indexOf[data[index]]==-1);
		indexOf[data[index]]=index;
	}

	for(int value=0; value<number; ++value){
		auto const index=indexOf[value];
		auto iterator=remaining.lower_bound(index);
		assert(iterator==remaining.end() or *iterator!=index);

		while(not remaining.empty()){
			if(iterator==remaining.begin()) iterator=remaining.end();
			--iterator;
			if((index-*iterator+number)%number<k){
				assert(result[*iterator]==-1);
				assert(*iterator!=index);
				result[*iterator]=index;
				iterator=remaining.erase(iterator);
			}else break;
		}

		remaining.insert(index);
	}
	return result;
}

void init(int k, std::vector<int> r) {
	::k=k;
	int const number=(int)r.size();
	Tree tree(number);
	std::set<int> okay;

	// functions to move okay's iterators around
	auto const prev=[&](auto it){ if(it==okay.begin()) it=okay.end(); return --it; };
	auto const wrap=[&](auto it){ return it==okay.end() ? okay.begin(): it; };

	auto const far=[&](int small, int large){
		assert(small!=large);
		return (large-small+number)%number>=k;
		// if handled carefully, it would be possible to remove the modulo by checking something equal to begin()/end() instead
	};
	std::set<int> veryOkay; // if a -> b are cyclic adjacent and far(a, b), then b is veryOkay

	auto const insertOkay=[&](int index){
		assert(tree.anyZero(index, index+1)==index);
		auto const [iterator, success]=okay.insert(index); assert(success);
		if(okay.size()==1){
			veryOkay.insert(index); return;
		}
		auto const p=prev(iterator), n=wrap(std::next(iterator));
		if(far(*p, index)) veryOkay.insert(index); else assert(veryOkay.count(index)==0);
		if(far(index, *n)) veryOkay.insert(*n); else veryOkay.erase(*n);
	};
	auto const eraseOkay=[&](int index){
		auto const n=wrap(okay.erase(okay.find(index)));
		veryOkay.erase(index);
		if(okay.empty()) return;

		if(okay.size()==1 or far(*prev(n), *n)) veryOkay.insert(*n); else veryOkay.erase(*n);
	};

	for(int i=0; i<number; ++i){
		if(r[i]!=0)
			tree.add(i, i+1, r[i]);
		else{
			insertOkay(i);
			tree.add(i, i+1, number*2);
		}
	}
	permutation.assign(number, -1);
	for(int value=number; value--;){
		assert(([&]{
			int last=*okay.rbegin();
			for(auto it: okay){
				assert((last==it or far(last, it))==veryOkay.count(it));
				last=it;
			}
		}(), true));
		auto const pos=*veryOkay.begin(); // pick an arbitrary element
		eraseOkay(pos);
		assert(tree.anyZero(pos, pos+1)==-1);
		assert(permutation[pos]==-1); permutation[pos]=value;

		auto const left=pos-k+1, right=pos;
		auto const process=[&](int left, int right){ // this function will be called with ranges (left, right) mod number
			tree.add(left, right, -1);
			int y;
			while((y=tree.anyZero(left, right))>=0){
				insertOkay(y);
				tree.add(y, y+1, number*2);
			}
		};

		if(left<0){
			process(left+number, number);
			process(0, right);
		}else process(left, right);
	}

	nextGreaterRight=jumpTable(nextGreater(k, permutation));

	permutationReversed=permutation;
	std::reverse(begin(permutationReversed), end(permutationReversed));
	nextGreaterLeft=jumpTable(nextGreater(k, permutationReversed));
}

bool increasingChain(int first, int sec, std::vector<std::vector<int>> const& jump, std::vector<int> const& data){
	for(auto layer=jump.size(); layer--;){
		auto const tmp=jump[layer][first];
		if(tmp<0) continue;
		if(first<sec ? tmp>=sec: (tmp>=sec and tmp<first)) continue;
		assert(data[first]<data[sec]);
		if(data[tmp]>=data[sec]) continue;
		first=tmp;
	}
	return (sec-first+(int)data.size())%(int)data.size()<k;
}

bool definitelyLess(int first, int sec){
	assert(permutation[first]<permutation[sec]);
	auto const number=(int)permutation.size();
	return increasingChain(first, sec, nextGreaterRight, permutation) or
		increasingChain(number-1-first, number-1-sec, nextGreaterLeft, permutationReversed);
}

int compare_plants(int x, int y) {
	if(permutation[x]<permutation[y])
		return definitelyLess(x, y) ? -1: 0;
	else
		return definitelyLess(y, x) ? 1: 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 77 ms 3192 KB Output is correct
7 Correct 135 ms 4908 KB Output is correct
8 Correct 443 ms 20752 KB Output is correct
9 Correct 493 ms 25548 KB Output is correct
10 Correct 554 ms 30276 KB Output is correct
11 Correct 605 ms 33984 KB Output is correct
12 Correct 644 ms 35652 KB Output is correct
13 Correct 661 ms 24620 KB Output is correct
14 Correct 630 ms 34004 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 121 ms 3960 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 121 ms 3960 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 384 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 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 77 ms 3192 KB Output is correct
7 Correct 135 ms 4908 KB Output is correct
8 Correct 443 ms 20752 KB Output is correct
9 Correct 493 ms 25548 KB Output is correct
10 Correct 554 ms 30276 KB Output is correct
11 Correct 605 ms 33984 KB Output is correct
12 Correct 644 ms 35652 KB Output is correct
13 Correct 661 ms 24620 KB Output is correct
14 Correct 630 ms 34004 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 288 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 121 ms 3960 KB Output is correct
22 Incorrect 3 ms 384 KB Output isn't correct
23 Halted 0 ms 0 KB -