oj.uz

Submission #260189

# Submission time Handle Problem Language Result Execution time Memory
260189 2020-08-09T15:12:54 Z user202729 Koala Game (APIO17_koala) C++17
88 / 100
 101 ms 636 KB 
// moreflags=grader.cpp
// 6
// :(
#include "koala.h"
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<cassert>
#include<algorithm>
#include<random>
#include<array>

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

Compilation message

koala.cpp: In lambda function:
koala.cpp:189:13: warning: variable 'useful' set but not used [-Wunused-but-set-variable]
        bool useful=false;
             ^~~~~~
koala.cpp:201:13: warning: variable 'useful' set but not used [-Wunused-but-set-variable]
        bool useful=false;
             ^~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 376 KB Output is correct
2 Correct 19 ms 256 KB Output is correct
3 Correct 19 ms 256 KB Output is correct
4 Correct 18 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 384 KB Output is correct
2 Correct 101 ms 408 KB Output is correct
3 Correct 81 ms 384 KB Output is correct
4 Correct 86 ms 636 KB Output is correct
5 Correct 83 ms 392 KB Output is correct
6 Correct 82 ms 384 KB Output is correct
7 Correct 89 ms 384 KB Output is correct
8 Correct 83 ms 384 KB Output is correct
9 Correct 82 ms 384 KB Output is correct
10 Correct 80 ms 384 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
51.0 / 53.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 384 KB Output is partially correct
2 Partially correct 9 ms 380 KB Output is partially correct
3 Partially correct 9 ms 384 KB Output is partially correct
4 Partially correct 8 ms 256 KB Output is partially correct
5 Partially correct 8 ms 256 KB Output is partially correct
6 Partially correct 8 ms 384 KB Output is partially correct
7 Partially correct 8 ms 384 KB Output is partially correct
8 Correct 7 ms 384 KB Output is correct
9 Partially correct 8 ms 256 KB Output is partially correct
10 Partially correct 8 ms 384 KB Output is partially correct
11 Partially correct 8 ms 384 KB Output is partially correct
12 Correct 8 ms 384 KB Output is correct
13 Correct 7 ms 256 KB Output is correct
14 Partially correct 8 ms 384 KB Output is partially correct
15 Partially correct 8 ms 384 KB Output is partially correct
16 Correct 7 ms 384 KB Output is correct
17 Partially correct 8 ms 256 KB Output is partially correct
18 Partially correct 8 ms 384 KB Output is partially correct
19 Partially correct 8 ms 384 KB Output is partially correct
20 Correct 7 ms 384 KB Output is correct
21 Partially correct 8 ms 256 KB Output is partially correct
22 Partially correct 8 ms 256 KB Output is partially correct
23 Partially correct 8 ms 380 KB Output is partially correct
24 Correct 8 ms 256 KB Output is correct
25 Partially correct 8 ms 384 KB Output is partially correct
26 Partially correct 9 ms 256 KB Output is partially correct
27 Partially correct 8 ms 384 KB Output is partially correct
28 Partially correct 8 ms 256 KB Output is partially correct
29 Partially correct 8 ms 256 KB Output is partially correct
30 Correct 7 ms 384 KB Output is correct
31 Correct 7 ms 384 KB Output is correct
32 Partially correct 7 ms 384 KB Output is partially correct
33 Partially correct 8 ms 256 KB Output is partially correct
34 Correct 8 ms 384 KB Output is correct
35 Partially correct 8 ms 384 KB Output is partially correct
36 Partially correct 8 ms 384 KB Output is partially correct
37 Partially correct 8 ms 256 KB Output is partially correct
38 Partially correct 8 ms 384 KB Output is partially correct
39 Partially correct 8 ms 384 KB Output is partially correct
40 Partially correct 8 ms 384 KB Output is partially correct