oj.uz

Submission #300633

# Submission time Handle Problem Language Result Execution time Memory
300633 2020-09-17T10:40:55 Z user202729 Comparing Plants (IOI20_plants) C++17
32 / 100
 760 ms 37876 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 or tmp<first): (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 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 69 ms 3192 KB Output is correct
7 Correct 130 ms 4916 KB Output is correct
8 Correct 437 ms 20672 KB Output is correct
9 Correct 479 ms 25548 KB Output is correct
10 Correct 565 ms 30256 KB Output is correct
11 Correct 620 ms 34112 KB Output is correct
12 Correct 642 ms 35680 KB Output is correct
13 Correct 636 ms 24616 KB Output is correct
14 Correct 623 ms 34012 KB Output is correct

Subtask #2
14.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 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 98 ms 3832 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 99 ms 3832 KB Output is correct
11 Correct 99 ms 3580 KB Output is correct
12 Correct 112 ms 3832 KB Output is correct
13 Correct 103 ms 3832 KB Output is correct

Subtask #3
13.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 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 98 ms 3832 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 99 ms 3832 KB Output is correct
11 Correct 99 ms 3580 KB Output is correct
12 Correct 112 ms 3832 KB Output is correct
13 Correct 103 ms 3832 KB Output is correct
14 Correct 142 ms 5820 KB Output is correct
15 Correct 715 ms 36436 KB Output is correct
16 Correct 153 ms 5948 KB Output is correct
17 Correct 712 ms 36344 KB Output is correct
18 Correct 680 ms 24572 KB Output is correct
19 Correct 682 ms 29396 KB Output is correct
20 Correct 742 ms 37876 KB Output is correct

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 Correct 99 ms 3448 KB Output is correct
4 Correct 760 ms 36472 KB Output is correct
5 Incorrect 731 ms 33236 KB Output isn't correct
6 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 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 18 ms 1024 KB Output is correct
8 Incorrect 22 ms 1024 KB Output isn't correct
9 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 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 426 ms 21588 KB Output is correct
7 Incorrect 524 ms 27092 KB Output isn't correct
8 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 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 69 ms 3192 KB Output is correct
7 Correct 130 ms 4916 KB Output is correct
8 Correct 437 ms 20672 KB Output is correct
9 Correct 479 ms 25548 KB Output is correct
10 Correct 565 ms 30256 KB Output is correct
11 Correct 620 ms 34112 KB Output is correct
12 Correct 642 ms 35680 KB Output is correct
13 Correct 636 ms 24616 KB Output is correct
14 Correct 623 ms 34012 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 256 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 98 ms 3832 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 99 ms 3832 KB Output is correct
25 Correct 99 ms 3580 KB Output is correct
26 Correct 112 ms 3832 KB Output is correct
27 Correct 103 ms 3832 KB Output is correct
28 Correct 142 ms 5820 KB Output is correct
29 Correct 715 ms 36436 KB Output is correct
30 Correct 153 ms 5948 KB Output is correct
31 Correct 712 ms 36344 KB Output is correct
32 Correct 680 ms 24572 KB Output is correct
33 Correct 682 ms 29396 KB Output is correct
34 Correct 742 ms 37876 KB Output is correct
35 Correct 1 ms 256 KB Output is correct
36 Correct 1 ms 256 KB Output is correct
37 Correct 99 ms 3448 KB Output is correct
38 Correct 760 ms 36472 KB Output is correct
39 Incorrect 731 ms 33236 KB Output isn't correct
40 Halted 0 ms 0 KB -