Submission #431851

#	Time	Username	Problem	Language	Result	Execution time	Memory
431851		frodakcin	Scales (IOI15_scales)	C++11	72.02 / 100	61 ms	324 KiB

scales

#include "scales.h"
#include <cassert>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <cstring>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

const int MN = 6;
const int MP = 6*5*4*3*2*1;

using arr = std::array<int, MN>;
arr p[MP];
struct move
{
	public:
		int type, v[3], D;
		int qry()
		{
			if(type==0)
				return getLightest(v[0], v[1], v[2]);
			if(type==1)
				return getMedian(v[0], v[1], v[2]);
			if(type==2)
				return getHeaviest(v[0], v[1], v[2]);
			if(type==3)
				return getNextLightest(v[0], v[1], v[2], D);
			assert(0);
			return -1;
		}
};
std::vector<move> moves;

void init(int T) {
	arr a;
	std::iota(a.begin(), a.end(), 1);
	int ctr=0;
	do
	{
		p[ctr++]=a;
	} while (std::next_permutation(a.begin(), a.end()));

	for(int i=1;i<=MN;++i)
		for(int j=i+1;j<=MN;++j)
			for(int k=j+1;k<=MN;++k)
			{
				moves.push_back({0, i, j, k, -1});
				moves.push_back({1, i, j, k, -1});
				moves.push_back({2, i, j, k, -1});
				for(int l=1;l<=MN;++l)
					if(l != i && l != j && l != k)
						moves.push_back({3, i, j, k, l});
			}
}

int get(const arr& a, const move& m)
{
	auto cmp=[&](int u, int v) {return a[u-1]<a[v-1];};
	int v[3] = {m.v[0], m.v[1], m.v[2]};
	std::sort(v, v+3, cmp);
	if(m.type == 3)
	{
		int x=m.D;
		for(int i=1;i<3;++i)
			if(cmp(v[i-1], x) && cmp(x, v[i]))
				return v[i];
		return v[0];
	}
	else
	{
		return v[m.type];
		/* //-- retrieve index
		for(int i=0;i<3;++i)
			if(m.v[i]==v[m.type])
				return i;
				*/
	}
	assert(0);
	return -1;
}

void orderCoins() {
    /* ... */
    int W[] = {1, 2, 3, 4, 5, 6};
		std::vector<arr> ok(p, p+MP), ok2;
		while(ok.size() > 1)
		{
			//printf("ok sz: %lu\n", ok.size());
			int id=-1, best=MP+1;
			for(int i=0;i<moves.size();++i)
			{
				int v[6]; memset(v, 0, sizeof v);
				for(const auto& x:ok)
					v[get(x, moves[i])-1]++;
				if(ckmin(best, *std::max_element(v, v+6)))
					id=i;
			}

			int q = moves[id].qry();
			//printf("Type %d: %d %d %d [%d]: %d\n", moves[id].type, moves[id].v[0], moves[id].v[1], moves[id].v[2] ,moves[id].D, q);
			for(const auto& x:ok)
				if(get(x, moves[id])==q)
					ok2.push_back(x);

			ok2.swap(ok);
			ok2.clear();
		}
		for(int i=0;i<6;++i)
			W[ok[0][i]-1]=i+1;
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:37:15: warning: unused parameter 'T' [-Wunused-parameter]
   37 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<move>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for(int i=0;i<moves.size();++i)
      |                ~^~~~~~~~~~~~~

• Subtask 1: 72.02381 / 100