Submission #1076918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076918		Elias	Scales (IOI15_scales)	C++17	100 / 100	139 ms	1268 KiB

scales

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
void init(int T);
void orderCoins();
void answer(int C[]);

int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
#else
#include "scales.h"
#endif

int all[] = {1, 3, 9, 27, 81, 243, 729, 729, 729, 729};

int pow3(int i)
{
return all[i];
}

void init(int T) {}

int getNLghtest(vector<int> &ind, int A, int B, int C, int D)
{
int allLess = 1;

if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
allLess = 0;

if (allLess == 1)
{
if (ind[A] < ind[B] && ind[A] < ind[C])
return A;

if (ind[B] < ind[A] && ind[B] < ind[C])
return B;

return C;
}

if (ind[A] > ind[D])
{
if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
(ind[A] < ind[C] || ind[C] < ind[D]))
return A;
}

if (ind[B] > ind[D])
{
if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
(ind[B] < ind[C] || ind[C] < ind[D]))
return B;
}

return C;
}

vector<int> result;

map<pair<int, vector<vector<int>>>, vector<int>> cache;

vector<int> solve(int depth, vector<vector<int>> possibilities, bool confirmed)
{
if (!confirmed)
{
if (cache.count({depth, possibilities}))
return cache[{depth, possibilities}];
}

if (possibilities.size() == 0)
{
assert(confirmed == false);
return cache[{depth, possibilities}] = {0};
}

if (possibilities.size() == 1)
{
if (confirmed)
return *possibilities.begin();
else
return cache[{depth, possibilities}] = {0};
}

if (depth == 0)
{
assert(confirmed == false);
return cache[{depth, possibilities}] = {};
}

for (int a = 1; a <= 6; a++)
for (int b = a + 1; b <= 6; b++)
for (int c = b + 1; c <= 6; c++)
{
	{
		vector<vector<int>> partition_a;
		vector<vector<int>> partition_b;
		vector<vector<int>> partition_c;

		for (auto poss : possibilities)
		{
			vector<int> ind(7);
			for (int i = 0; i < 6; i++)
				ind[poss[i]] = i;

			if (ind[a] < ind[b] && ind[a] < ind[c])
				partition_a.push_back(poss);
			else if (ind[b] < ind[a] && ind[b] < ind[c])
				partition_b.push_back(poss);
			else if (ind[c] < ind[a] && ind[c] < ind[b])
				partition_c.push_back(poss);
			else
				assert(false);
		}

		if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
		{
			if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
			{
				if (confirmed)
				{
					int result = getLightest(a, b, c);
					if (result == a)
						return solve(depth - 1, partition_a, true);
					if (result == b)
						return solve(depth - 1, partition_b, true);
					if (result == c)
						return solve(depth - 1, partition_c, true);
				}
				else
				{
					return cache[{depth, possibilities}] = {0};
				}

				assert(false);
			}
		}
	}

	{
		vector<vector<int>> partition_a;
		vector<vector<int>> partition_b;
		vector<vector<int>> partition_c;

		for (auto poss : possibilities)
		{
			vector<int> ind(7);
			for (int i = 0; i < 6; i++)
				ind[poss[i]] = i;

			if ((ind[a] > ind[b] && ind[a] < ind[c]) || (ind[a] < ind[b] && ind[a] > ind[c]))
			{
				partition_a.push_back(poss);
			}
			else if ((ind[b] > ind[c] && ind[b] < ind[a]) || (ind[b] < ind[c] && ind[b] > ind[a]))
			{
				partition_b.push_back(poss);
			}
			else if ((ind[c] > ind[a] && ind[c] < ind[b]) || (ind[c] < ind[a] && ind[c] > ind[b]))
			{
				partition_c.push_back(poss);
			}
			else
			{
				assert(false);
			}
		}

		if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
		{
			if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
			{
				if (confirmed)
				{
					int result = getMedian(a, b, c);
					if (result == a)
						return solve(depth - 1, partition_a, true);
					if (result == b)
						return solve(depth - 1, partition_b, true);
					if (result == c)
						return solve(depth - 1, partition_c, true);
				}
				else
				{
					return cache[{depth, possibilities}] = {0};
				}

				assert(false);
			}
		}
	}

	{
		vector<vector<int>> partition_a;
		vector<vector<int>> partition_b;
		vector<vector<int>> partition_c;

		for (auto poss : possibilities)
		{
			vector<int> ind(7);
			for (int i = 0; i < 6; i++)
				ind[poss[i]] = i;

			if (ind[a] > ind[b] && ind[a] > ind[c])
			{
				partition_a.push_back(poss);
			}
			else if (ind[b] > ind[a] && ind[b] > ind[c])
			{
				partition_b.push_back(poss);
			}
			else if (ind[c] > ind[a] && ind[c] > ind[b])
			{
				partition_c.push_back(poss);
			}
			else
			{
				assert(false);
			}
		}

		if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
		{
			if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
			{
				if (confirmed)
				{
					int result = getHeaviest(a, b, c);
					if (result == a)
						return solve(depth - 1, partition_a, true);
					if (result == b)
						return solve(depth - 1, partition_b, true);
					if (result == c)
						return solve(depth - 1, partition_c, true);
				}
				else
				{
					return cache[{depth, possibilities}] = {0};
				}

				assert(false);
			}
		}
	}

	for (int d = 1; d <= 6; d++)
	{
		if (d == a || d == b || d == c)
			continue;

		{
			vector<vector<int>> partition_a;
			vector<vector<int>> partition_b;
			vector<vector<int>> partition_c;

			for (auto poss : possibilities)
			{
				vector<int> ind(7);
				for (int i = 0; i < 6; i++)
					ind[poss[i]] = i;

				int result = getNLghtest(ind, a, b, c, d);

				if (result == a)
					partition_a.push_back(poss);
				else if (result == b)
					partition_b.push_back(poss);
				else if (result == c)
					partition_c.push_back(poss);
				else
					assert(false);
			}

			if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
			{
				if (solve(depth - 1, partition_a, false).size() && solve(depth - 1, partition_b, false).size() && solve(depth - 1, partition_c, false).size())
				{
					if (confirmed)
					{
						int result = getNextLightest(a, b, c, d);
						if (result == a)
							return solve(depth - 1, partition_a, true);
						if (result == b)
							return solve(depth - 1, partition_b, true);
						if (result == c)
							return solve(depth - 1, partition_c, true);
					}
					else
					{
						return cache[{depth, possibilities}] = {0};
					}

					assert(false);
				}
			}
		}
	}
}
return cache[{depth, possibilities}] = {};
}

void orderCoins()
{
vector<vector<int>> possibilities;
vector<int> a = {1, 2, 3, 4, 5, 6};
do
{
possibilities.push_back(a);
} while (next_permutation(a.begin(), a.end()));

auto result = solve(6, possibilities, true);
answer(&result[0]);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:30:15: warning: unused parameter 'T' [-Wunused-parameter]
   30 | void init(int T) {}
      |           ~~~~^
scales.cpp: In function 'std::vector<int> solve(int, std::vector<std::vector<int> >, bool)':
scales.cpp:124:73: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  124 |   if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:130:10: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  130 |      int result = getLightest(a, b, c);
      |          ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:177:73: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  177 |   if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:183:10: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  183 |      int result = getMedian(a, b, c);
      |          ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:230:73: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  230 |   if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:236:10: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  236 |      int result = getHeaviest(a, b, c);
      |          ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:270:9: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  270 |     int result = getNLghtest(ind, a, b, c, d);
      |         ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp:282:74: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
  282 |    if (max({partition_a.size(), partition_b.size(), partition_c.size()}) <= pow3(depth - 1))
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:288:11: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  288 |       int result = getNextLightest(a, b, c, d);
      |           ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:319:6: warning: declaration of 'result' shadows a global declaration [-Wshadow]
  319 | auto result = solve(6, possibilities, true);
      |      ^~~~~~
scales.cpp:67:13: note: shadowed declaration is here
   67 | vector<int> result;
      |             ^~~~~~

• Subtask 1: 100 / 100