Submission #300737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300737	2020-09-17T12:53:56 Z	user202729	Comparing Plants (IOI20_plants)	C++17	100 / 100	917 ms	36488 KB

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

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.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	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	68 ms	3192 KB	Output is correct
7	Correct	134 ms	5040 KB	Output is correct
8	Correct	457 ms	20752 KB	Output is correct
9	Correct	498 ms	25408 KB	Output is correct
10	Correct	591 ms	30148 KB	Output is correct
11	Correct	651 ms	33980 KB	Output is correct
12	Correct	673 ms	35612 KB	Output is correct
13	Correct	710 ms	24656 KB	Output is correct
14	Correct	662 ms	34000 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	360 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	256 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	92 ms	3480 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	100 ms	3576 KB	Output is correct
11	Correct	100 ms	3576 KB	Output is correct
12	Correct	105 ms	3832 KB	Output is correct
13	Correct	83 ms	3448 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	360 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	256 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	92 ms	3480 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	100 ms	3576 KB	Output is correct
11	Correct	100 ms	3576 KB	Output is correct
12	Correct	105 ms	3832 KB	Output is correct
13	Correct	83 ms	3448 KB	Output is correct
14	Correct	117 ms	4156 KB	Output is correct
15	Correct	599 ms	15992 KB	Output is correct
16	Correct	122 ms	4572 KB	Output is correct
17	Correct	586 ms	17532 KB	Output is correct
18	Correct	744 ms	24612 KB	Output is correct
19	Correct	715 ms	29340 KB	Output is correct
20	Correct	569 ms	16020 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	288 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	100 ms	3424 KB	Output is correct
4	Correct	791 ms	36372 KB	Output is correct
5	Correct	794 ms	32276 KB	Output is correct
6	Correct	778 ms	26964 KB	Output is correct
7	Correct	617 ms	22228 KB	Output is correct
8	Correct	585 ms	17620 KB	Output is correct
9	Correct	695 ms	24652 KB	Output is correct
10	Correct	917 ms	33764 KB	Output is correct
11	Correct	674 ms	24612 KB	Output is correct
12	Correct	719 ms	34136 KB	Output is correct
13	Correct	745 ms	24616 KB	Output is correct

Subtask #5

11.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	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	18 ms	896 KB	Output is correct
8	Correct	17 ms	1024 KB	Output is correct
9	Correct	19 ms	1024 KB	Output is correct
10	Correct	18 ms	1024 KB	Output is correct
11	Correct	18 ms	1024 KB	Output is correct
12	Correct	18 ms	1024 KB	Output is correct
13	Correct	17 ms	1024 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 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	2 ms	384 KB	Output is correct
6	Correct	434 ms	21588 KB	Output is correct
7	Correct	540 ms	23764 KB	Output is correct
8	Correct	564 ms	19060 KB	Output is correct
9	Correct	559 ms	16120 KB	Output is correct
10	Correct	415 ms	24536 KB	Output is correct
11	Correct	483 ms	25044 KB	Output is correct
12	Correct	579 ms	36400 KB	Output is correct
13	Correct	523 ms	32368 KB	Output is correct
14	Correct	597 ms	27044 KB	Output is correct
15	Correct	548 ms	22232 KB	Output is correct
16	Correct	770 ms	34124 KB	Output is correct
17	Correct	533 ms	29484 KB	Output is correct

Subtask #7

25.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	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	68 ms	3192 KB	Output is correct
7	Correct	134 ms	5040 KB	Output is correct
8	Correct	457 ms	20752 KB	Output is correct
9	Correct	498 ms	25408 KB	Output is correct
10	Correct	591 ms	30148 KB	Output is correct
11	Correct	651 ms	33980 KB	Output is correct
12	Correct	673 ms	35612 KB	Output is correct
13	Correct	710 ms	24656 KB	Output is correct
14	Correct	662 ms	34000 KB	Output is correct
15	Correct	0 ms	256 KB	Output is correct
16	Correct	1 ms	360 KB	Output is correct
17	Correct	1 ms	256 KB	Output is correct
18	Correct	1 ms	256 KB	Output is correct
19	Correct	1 ms	256 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	92 ms	3480 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	4 ms	384 KB	Output is correct
24	Correct	100 ms	3576 KB	Output is correct
25	Correct	100 ms	3576 KB	Output is correct
26	Correct	105 ms	3832 KB	Output is correct
27	Correct	83 ms	3448 KB	Output is correct
28	Correct	117 ms	4156 KB	Output is correct
29	Correct	599 ms	15992 KB	Output is correct
30	Correct	122 ms	4572 KB	Output is correct
31	Correct	586 ms	17532 KB	Output is correct
32	Correct	744 ms	24612 KB	Output is correct
33	Correct	715 ms	29340 KB	Output is correct
34	Correct	569 ms	16020 KB	Output is correct
35	Correct	1 ms	288 KB	Output is correct
36	Correct	1 ms	256 KB	Output is correct
37	Correct	100 ms	3424 KB	Output is correct
38	Correct	791 ms	36372 KB	Output is correct
39	Correct	794 ms	32276 KB	Output is correct
40	Correct	778 ms	26964 KB	Output is correct
41	Correct	617 ms	22228 KB	Output is correct
42	Correct	585 ms	17620 KB	Output is correct
43	Correct	695 ms	24652 KB	Output is correct
44	Correct	917 ms	33764 KB	Output is correct
45	Correct	674 ms	24612 KB	Output is correct
46	Correct	719 ms	34136 KB	Output is correct
47	Correct	745 ms	24616 KB	Output is correct
48	Correct	1 ms	256 KB	Output is correct
49	Correct	1 ms	256 KB	Output is correct
50	Correct	1 ms	256 KB	Output is correct
51	Correct	1 ms	256 KB	Output is correct
52	Correct	1 ms	256 KB	Output is correct
53	Correct	3 ms	384 KB	Output is correct
54	Correct	18 ms	896 KB	Output is correct
55	Correct	17 ms	1024 KB	Output is correct
56	Correct	19 ms	1024 KB	Output is correct
57	Correct	18 ms	1024 KB	Output is correct
58	Correct	18 ms	1024 KB	Output is correct
59	Correct	18 ms	1024 KB	Output is correct
60	Correct	17 ms	1024 KB	Output is correct
61	Correct	84 ms	3192 KB	Output is correct
62	Correct	123 ms	4284 KB	Output is correct
63	Correct	471 ms	17668 KB	Output is correct
64	Correct	593 ms	22356 KB	Output is correct
65	Correct	753 ms	23928 KB	Output is correct
66	Correct	580 ms	19164 KB	Output is correct
67	Correct	584 ms	15956 KB	Output is correct
68	Correct	639 ms	24836 KB	Output is correct
69	Correct	536 ms	25172 KB	Output is correct
70	Correct	826 ms	36488 KB	Output is correct
71	Correct	870 ms	32344 KB	Output is correct
72	Correct	759 ms	27028 KB	Output is correct
73	Correct	617 ms	22228 KB	Output is correct
74	Correct	479 ms	19804 KB	Output is correct
75	Correct	783 ms	30164 KB	Output is correct