| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 260188 | user202729 | Koala Game (APIO17_koala) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// moreflags=grader.cpp
// 6
// :(
#include "koala.h"
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<cassert>
#include<algorithm>
#include<random>
#if LOCAL
#include<cstdio>
#endif
std::vector<int>& play(std::vector<int>& data, std::vector<int>& result){
assert(result.size()==data.size());
playRound(data.data(), result.data());
return result;
}
std::vector<int> play(std::vector<int>& data){
std::vector<int> result(data.size());
play(data, result);
return result;
}
int minValue(int N, int W) {
assert(N==W);
std::vector<int> data(N);
data[0]=1;
auto result=play(data);
for(int i=0; i<N; ++i)
if(result[i]<=data[i])
return i;
}
int maxValue(int N, int W) {
assert(N==W);
std::vector<int> data(N, 1);
std::vector<int> result(N);
while(true){
auto c=(int)std::count_if(begin(data), end(data),[&](int it){return it>0;});
if(c==1)
return int(std::find_if(begin(data), end(data),[&](int it){return it>0;})-data.begin());
/*
int value=W/c;
while([&]{
int tmp=0;
for(int i=N-c; i>N-c-value; --i) tmp+=i;
return tmp;
}()>=N) {
--value;
assert(value>=1);
}
*/
for(auto& it: data)
if(it>0) it=W/c;
play(data, result);
for(int i=0; i<N; ++i)
if(result[i]<=data[i])
data[i]=0;
}
}
int greaterValue_(int N, int W, int first, int sec){ // return 0 if first is greater
assert(N==W);
std::vector<int> data(N), result(N);
auto const check=[&](int value){
assert(value>0);
value+=value>=6;
data[first]=data[sec]=value;
play(data, result);
if(result[first]>data[first] and result[sec]>data[sec]){
return 2;
}else if(result[first]<=data[first] and result[sec]<=data[sec]){
return 0;
}else{
return 1;
}
};
#if 0
for(int i=1; i<12; ++i)
std::fprintf(stderr, "%d", check(i));
std::fprintf(stderr, "\n");
return 0;
#endif
int k=0;
for(auto step=1<<3;;){
step>>=1;
assert(step!=0);
switch(check(k+step)){
case 2: k+=step; break;
case 0: break;
case 1:
if(result[first]>data[first]) return 0; else return 1;
}
}
}
int greaterValue(int N, int W) {
return greaterValue_(N, W, 0, 1);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
} else {
std::vector<int> data(N), result(N);
std::vector<char> split(N); split[0]=true;
std::fill(P, P+N, 1);
auto const value=[&](unsigned index)->int&{ assert(index<(unsigned)N); return P[index]; };
auto const findIncrement=[&]{
for(int i=1; i*2+1<=N; ++i){
assert(split[i-1]);
if(not split[i]){
for(int index=0; index<N; ++index)
data[index]=value(index)<i ? 1: 0;
for(int index=0, left=i; left; ++index) if(data[index]==0){
data[index]=1; --left;
}
play(data, result);
auto const condition=[&](int index){ return value(index)>=i and result[index]<=data[index]; };
assert([&]{
int count=0;
for(int index=0; index<N; ++index) count+=condition(index);
assert(count==1); return true;
}());
for(int index=0;; ++index) if(condition(index)){
for(int j=0; j<N; ++j)
if(value(j)==i) value(j)=i+1;
assert(value(index)==i+1);
value(index)=i;
break;
}
assert(split[i-1]); assert(not split[i]); split[i]=true;
return true;
}
}
return false;
};
auto const done=[&]{return std::all_of(begin(split), end(split),[&](char it){return it;});};
auto const find=[&](int threshold){
assert(threshold>=1 and threshold<=2);
assert(not done());
for(int i=0; i<N; ++i) assert(split[value(i)-1]);
for(int split0=0; split0<N; ++split0) if(split[split0]){
// value (1..=split0) -> 0, (split0+1..=N) -> 1
for(int weight=1; weight*(N-split0)<=W; ++weight){
int const redWeight=weight+1;
std::array<int, 4> resultDistribution{}; resultDistribution[0]=-1;
for(int left=(W-split0)/redWeight,
right=std::min(W/redWeight, N-split0)+1,
numRed1=left; numRed1<right; ++numRed1){ // TODO inefficient
int numRed0=std::min(split0, W-numRed1*redWeight);
assert(numRed0>=0); assert(numRed1>=0);
resultDistribution=std::max(resultDistribution, std::array<int, 4>{{
(numRed1*(N+N-numRed1+1)+numRed0*(split0+split0-numRed0+1))>>1,
numRed0+numRed1,
split0-numRed0, N-numRed1}});
}
assert(resultDistribution[0]>=0);
if(resultDistribution[3]<N and (not split[resultDistribution[2]])
+(not split[resultDistribution[3]])>=threshold){
for(int index=0; index<N; ++index)
data[index]=value(index)>=split0+1 ? weight: 0;
play(data, result);
assert(not split[resultDistribution[2]] or not split[resultDistribution[3]]);
if(not split[resultDistribution[2]]){
bool useful=false;
auto lastSplitp1=resultDistribution[2];
while(not split[lastSplitp1-1]) --lastSplitp1;
for(int index=0; index<N; ++index)
if(data[index]==0 and result[index]>data[index] and value(index)==lastSplitp1){
value(index)=resultDistribution[2]+1;
useful=true;
}
assert(useful);
split[resultDistribution[2]]=true;
}
if(not split[resultDistribution[3]]){
bool useful=false;
auto lastSplitp1=resultDistribution[3];
while(not split[lastSplitp1-1]) --lastSplitp1;
for(int index=0; index<N; ++index)
if(data[index]!=0 and result[index]>data[index] and value(index)==lastSplitp1){
value(index)=resultDistribution[3]+1;
useful=true;
}
assert(useful);
split[resultDistribution[3]]=true;
}
return true;
}
}
}
return false;
};
auto const splitBlock=[&]{
static std::mt19937 engine(123);
int left=0;
while(split[left]) ++left;
int right=left;
do ++right; while(not split[right]);
++right;
std::vector<int> indices; indices.reserve(right-left);
for(int index=0; index<N; ++index) if(left==value(index))
indices.push_back(index);
else assert(value(index)<left or value(index)>=right);
assert((int)indices.size()==(right-left));
std::swap(indices[0], indices[std::uniform_int_distribution<int>(0, (int)indices.size()-1)(engine)]);
auto const iterator=std::partition(1+begin(indices), end(indices),[&](auto it){
return greaterValue_(N, W, indices[0], it);
});
auto const numSmall=int(indices.end()-iterator);
std::for_each(indices.begin()+1, iterator,[&](int index){ value(index)=left+numSmall+1; });
std::for_each(iterator, indices.end(), [&](int index){ assert(value(index)==left); });
value(indices[0])=left+numSmall;
assert(split[left-1]); assert(split[right-1]);
split[left+numSmall-1]=true;
split[left+numSmall]=true;
};
while(not done()){
if(not find(2)){
if(not(find(1) || findIncrement()))
splitBlock();
}else{
#if LOCAL
//std::fprintf(stderr, "??\n");
#endif
}
}
}
}