Submission #60798

#	Time	Username	Problem	Language	Result	Execution time	Memory
60798		Eae02	Scales (IOI15_scales)	C++14	4.98 / 100	8 ms	764 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[7];
	for (int i = 0; i < 6; i++)
	{
		indexOf[x & 7] = i;
		x >>= 3;
	}
	
	for (const Condition& c : cond)
	{
		if (!(indexOf[c.l] < indexOf[c.g]))
			return false;
	}
	return true;
}

std::bitset<2 << 9> done[2];

void orderCoins()
{
	cond.clear();
	done[0].reset();
	done[1].reset();
	std::set<uint32_t> possible = possibleInitial;
	
	int N[6] = { 1, 2, 3, 4, 5, 6 };
	while (possible.size() > 1)
	{
		std::random_shuffle(N, N + 6);
		int type = rand() % 2;
		
		uint32_t qIndex = N[0] | (N[1] << 3) | (N[2] << 6);
		if (done[type][qIndex])
			continue;
		done[type][qIndex] = true;
		
		int v;
		if (type)
		{
			v = getHeaviest(N[0], N[1], N[2]);
		}
		else
		{
			v = getLightest(N[0], N[1], N[2]);
		}
		
		int o1, o2;
		if (v == N[0])
		{
			o1 = N[1];
			o2 = N[2];
		}
		else if (v == N[1])
		{
			o1 = N[0];
			o2 = N[2];
		}
		else if (v == N[2])
		{
			o1 = N[0];
			o2 = N[1];
		}
		
		if (type)
		{
			cond.emplace(o1, v);
			cond.emplace(o2, v);
		}
		else
		{
			cond.emplace(v, o1);
			cond.emplace(v, o2);
		}
		
		for (auto it = possible.begin(); it != possible.end(); ++it)
		{
			if (!works(*it))
				possible.erase(it);
		}
		
		//std::cout << possible.size() << std::endl;
	}
	
	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: 4.981916 / 100