Submission #60809

#	Time	Username	Problem	Language	Result	Execution time	Memory
60809		Eae02	Scales (IOI15_scales)	C++14	25.21 / 100	6 ms	696 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() = default;
	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;
	}
};

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

#define all(x) x.begin(),x.end()

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

void orderCoins()
{
	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)
		{
			bool good = true;
			for (int i = 0; i < 3; i++)
			{
				Condition extra[2] = { { N[(i + 1) % 3], N[i] }, { N[(i + 2) % 3], N[i] } };
				if (!std::any_of(all(possible), [&] (uint32_t p) { return !works(p, extra, 2); }))
				{
					good = false;
					break;
				}
			}
			
			if (!good)
				continue;
			
			v = getHeaviest(N[0], N[1], N[2]);
		}
		else
		{
			bool good = true;
			for (int i = 0; i < 3; i++)
			{
				Condition extra[2] = { { N[i], N[(i + 1) % 3] }, { N[i], N[(i + 2) % 3] } };
				if (!std::any_of(all(possible), [&] (uint32_t p) { return !works(p, extra, 2); }))
				{
					good = false;
					break;
				}
			}
			
			if (!good)
				continue;
			
			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];
		}
		
		Condition cond[2];
		if (type)
		{
			cond[0] = { o1, v };
			cond[1] = { o2, v };
		}
		else
		{
			cond[0] = { v, o1 };
			cond[1] = { v, o2 };
		}
		
		for (auto it = possible.begin(); it != possible.end(); ++it)
		{
			if (!works(*it, cond, 2))
				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)
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:56:41: warning: 'o2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (!(indexOf[c[i].l] < indexOf[c[i].g]))
                           ~~~~~~~~~~~~~~^
scales.cpp:122:11: note: 'o2' was declared here
   int o1, o2;
           ^~
scales.cpp:56:41: warning: 'o1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (!(indexOf[c[i].l] < indexOf[c[i].g]))
                           ~~~~~~~~~~~~~~^
scales.cpp:122:7: note: 'o1' was declared here
   int o1, o2;
       ^~

• Subtask 1: 25.206767 / 100