Submission #289747

#	Time	Username	Problem	Language	Result	Execution time	Memory
289747		user202729	Scales (IOI15_scales)	C++17	100 / 100	28 ms	624 KiB

scales

// moreflags=grader.cpp
//
// 10
// In retrospect, there's a much easier way in this particular case.
// For a more complex search algorithm, this might not be possible.
#include "scales.h"
#include<array>
#include<algorithm>
#include<bitset>
#include<numeric>
#include<climits>
#include<random>
#include<iostream>
#if LOCAL
#else
#define NDEBUG
#endif
#include<cassert>


using P=std::array<unsigned char, 6>;
using M=std::bitset<720>;

struct Query{
	int type;
	std::array<unsigned char, 4> parameter;
	int operator()(P it) const{
		std::array<std::pair<unsigned char, unsigned char>, 3> pairs;
		for(int index=0; index<3; ++index)
			pairs[index]={it[parameter[index]], index};
		std::sort(begin(pairs), end(pairs),[&](auto first, auto sec){return first.first<sec.first;});
		if(type==3){
			auto const cut=it[parameter[3]];
			for(auto [value, index]: pairs) if(value>cut) return index;
			return pairs[0].second;
		}
		return pairs[type].second;
	}

	int get(){
		auto const process=[&](auto function){
			auto const result=function(parameter[0]+1, parameter[1]+1, parameter[2]+1)-1;
			for(int index=0;; ++index){
				assert(index<3);
				if(result==parameter[index]) return index;
			}
		};
		auto const process4=[&](auto function){
			auto const result=function(parameter[0]+1, parameter[1]+1, parameter[2]+1, parameter[3]+1)-1;
			for(int index=0;; ++index){
				assert(index<3);
				if(result==parameter[index]) return index;
			}
		};
		switch(type){
			case 0:
				return process(getLightest);
			case 1:
				return process(getMedian);
			case 2:
				return process(getHeaviest);
			case 3:
				return process4(getNextLightest);
			default:
				assert(false); __builtin_unreachable();
		}
	}
};

int const numLayer=6;
std::array<P, 720> permutations_;
std::array<int, numLayer+1> pow3;
std::vector<int> layerOf;
std::vector<M> masks;
std::vector<Query> bestQuery;


void init(int T) {

	{
		P it; std::iota(begin(it), end(it), 0);
		int index=0;
		do{
			permutations_[index++]=it;
		}while(std::next_permutation(begin(it), end(it)));
	}
	auto const get=[&](int index)->P{return permutations_[index];};


	for(int index=0, value=1; index<(int)pow3.size(); ++index, value*=3)
		pow3[index]=value;

	//for(int layer=0; layer<=numLayer; ++layer)
	for(int layer=numLayer; layer>=0; --layer)
		layerOf.insert(layerOf.end(), pow3[numLayer-layer], layer);
	masks.resize(layerOf.size());
	bestQuery.resize(layerOf.size());
	masks[0]=~ M{};

	int seed=9887;
	// 37 seconds to find this value
	auto const process=[&]{
		std::mt19937 engine(++seed);
		for(int index=0; index*3+3<(int)masks.size(); ++index){
			Query best;
			int bestValue=INT_MAX;
			int numFound=1;

			auto const process=[&](Query query){
				std::array<M, 3> split{};
				for(auto index2=masks[index]._Find_first(); index2<masks[index].size();
						index2=masks[index]._Find_next(index2)){
					split[query(get((int)index2))][index2]=true;
				}

				int curValue{};
				for(auto it: split) curValue=std::max(curValue, (int)it.count());
				if(curValue<bestValue){ bestValue=curValue; best=query; numFound=1; }
				else if(curValue==bestValue){
					if(std::uniform_int_distribution(0, numFound++)(engine)==0)
						best=query;
				}
				return split;
			};

			/*
			if(layerOf[index]>=numLayer){
				process(Query{0, {{0, 1, 2}}});
			}else if(layerOf[index]>=numLayer-1){
				process(Query{0, {{3, 4, 5}}});
			}else{
			*/
			{
				for(unsigned char a=2; a<6; ++a)
					for(unsigned char b=1; b<a; ++b)
						for(unsigned char c=0; c<b; ++c){
							for(int type=0; type<3; ++type)
								process(Query{type, {{a, b, c}}});
							for(unsigned char d=0; d<c; ++d){
								process(Query{3, {{a, b, c, d}}});
								process(Query{3, {{a, b, d, c}}});
								process(Query{3, {{a, d, c, b}}});
								process(Query{3, {{d, b, c, a}}});
							}
						}
			}

			assert(bestValue!=INT_MAX);
			if(bestValue>pow3[layerOf[index]-1]){
				return false;
			}
			auto const tmp=process(best);
			bestQuery[index]=best;
			for(int i=0; i<3; ++i)
				masks[index*3+i+1]=std::move(tmp[i]);
		}
		return true;
	};
	while(not process()){
		// assert(false);
	}
	//std::cerr<<seed<<'\n';
}

void orderCoins() {
	int node=0;
	while(masks[node].count()!=1)
		node=node*3+1+bestQuery[node].get();

	auto result_=permutations_[masks[node]._Find_first()];
	std::array<int, 6> result;
	for(int i=0; i<6; ++i)
		result[result_[i]]=i+1;
    answer(result.data());
}

Compilation message (stderr)

scales.cpp: In lambda function:
scales.cpp:109:15: warning: declaration of 'process' shadows a previous local [-Wshadow]
  109 |    auto const process=[&](Query query){
      |               ^~~~~~~
scales.cpp:102:13: note: shadowed declaration is here
  102 |  auto const process=[&]{
      |             ^~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:78:15: warning: unused parameter 'T' [-Wunused-parameter]
   78 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100