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