Submission #289364

#	Time	Username	Problem	Language	Result	Execution time	Memory
289364		user202729	Scales (IOI15_scales)	C++17	71.43 / 100	58 ms	672 KiB

scales

// moreflags=grader.cpp
//
// 10
#include "scales.h"
#include<array>
#include<algorithm>
#include<bitset>
#include<numeric>
#include<climits>
#if LOCAL
//#include<iostream>
#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=7;
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{};

	for(int index=0; index*3+3<(int)masks.size(); ++index){
		Query best;
		int bestValue=INT_MAX;

		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; }
			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);
		assert(bestValue<=pow3[layerOf[index]-1]);
		auto const tmp=process(best);
		bestQuery[index]=best;
		for(int i=0; i<3; ++i)
			masks[index*3+i+1]=std::move(tmp[i]);
	}
}

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 function 'void init(int)':
scales.cpp:75:15: warning: unused parameter 'T' [-Wunused-parameter]
   75 | void init(int T) {
      |           ~~~~^

• Subtask 1: 71.428571 / 100