Submission #60778

#	Time	Username	Problem	Language	Result	Execution time	Memory
60778		Eae02	Scales (IOI15_scales)	C++14	0 / 100	1086 ms	812 KiB

scales

#include "scales.h"

#include <bits/stdc++.h>

std::set<uint32_t> possibleInitial;

uint32_t getIndex(int* N)
{
	uint32_t m = 0;
	for (int i = 0; i < 6; i++)
	{
		m |= N[i] << (i * 3);
	}
	return m;
}

void init(int T)
{
	int N[6] = { 1, 2, 3, 4, 5, 6 };
	do
	{
		possibleInitial.insert(getIndex(N));
	} while (std::next_permutation(N, N + 6));
}

struct Condition
{
	int l;
	int g;
	
	Condition(int _l, int _g) : l(_l), g(_g) { }
	
	inline bool operator<(const Condition& other) const
	{
		return l == other.l ? g < other.g : l < other.l;
	}
	
	inline bool operator==(const Condition& other) const
	{
		return l == other.l && g == other.g;
	}
};

std::set<Condition> cond;

bool works(uint32_t x)
{
	int indexOf[6];
	for (int i = 0; i < 6; i++)
	{
		indexOf[(x & 7) - 1] = i;
		x >>= 3;
	}
	
	for (const Condition& c : cond)
	{
		if (!(indexOf[c.l] < indexOf[c.g]))
			return false;
	}
	return true;
}

void orderCoins()
{
	std::set<uint32_t> possible = possibleInitial;
	
	int N[6] = { 1, 2, 3, 4, 5, 6 };
	while (!possible.empty())
	{
		std::random_shuffle(N, N + 6);
		int h = getHeaviest(N[0], N[1], N[2]);
		int m = getMedian(N[0], N[1], N[2]);
		
		int l;
		if ((h == N[0] || m == N[0]) && (h == N[1] || m == N[1]))
			l = N[2];
		else if ((h == N[0] || m == N[0]) && (h == N[2] || m == N[2]))
			l = N[1];
		else// if ((h == N[2] || m == N[2]) && (h == N[1] || m == N[1]))
			l = N[0];
		
		cond.emplace(l, h);
		cond.emplace(m, h);
		cond.emplace(l, m);
		
		for (auto it = possible.begin(); it != possible.end(); ++it)
		{
			if (!works(*it))
				possible.erase(it);
		}
	}
	
	uint32_t val = *possible.begin();
	
	int resp[6];
	for (int i = 0; i < 6; i++)
	{
		resp[i] = val & 7;
		val >>= 3;
	}
	answer(resp);
}

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:17:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^

• Subtask 1: 0 / 100