Submission #300737

#	Time	Username	Problem	Language	Result	Execution time	Memory
300737		user202729	Comparing Plants (IOI20_plants)	C++17	100 / 100	917 ms	36488 KiB

plants

// moreflags=grader.cpp
// really...
// I can't even debug it without writing a test case generator and figuring out which assertions to add to the program.


#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
	int const number=data.size();
	std::vector<std::vector<int>> result{std::move(data)};
	while(true){
		std::vector<int> next=result.back();
		bool useful=false;
		for(int index=0; index<number; ++index){
			auto& it=next[index];
			if(it>=0){
				auto const tmp=result.back()[it];
				it=((tmp-index+number)%number>(it-index+number)%number) ? tmp: -1;
				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; // items < current value with result not filled (-1)
	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];

		// fill the remaining in index's range
		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);
	}

	assert(([&]{
		for(int index=0; index<number; ++index){
			if(result[index]==-1){
				for(int j=1; j<k; ++j)
					assert(data[index]>data[(index+j)%number]);
			}else{
				assert(data[result[index]]>=data[index]);
				for(int j=1; j<k; ++j)
					assert(
							(data[(index+j)%number]>=data[result[index]]) xor
							(data[(index+j)%number]<data[index])
							);
			}
		}
		return true;
	}()));
	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));

	for(auto it: permutation) assert(std::cerr<<it<<' ');
	assert(std::cerr<<'\n');

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

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

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;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:235:11: warning: unused variable 'it' [-Wunused-variable]
  235 |  for(auto it: permutation) assert(std::cerr<<it<<' ');
      |           ^~
plants.cpp: In function 'bool increasingChain(int, int, const std::vector<std::vector<int> >&, const std::vector<int>&)':
plants.cpp:244:13: warning: unused variable 'oldFirst' [-Wunused-variable]
  244 |  auto const oldFirst=first;
      |             ^~~~~~~~

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