Submission #1034656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034656		fv3	Scales (IOI15_scales)	C++14	71.43 / 100	151 ms	604 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

void init(int T) 
{
    /* ... */
}

bool isGreater(vector<int>& v, int A, int B, int C)
{
	for (int i = 5; i >= 0; i--)
	{
		if (v[i] == B || v[i] == C)
			return 0;
		if (v[i] == A) return 1;
	}
	return 0;
}

bool isLess(vector<int>& v, int A, int B, int C)
{
	for (int i = 0; i < 6; i++)
	{
		if (v[i] == B || v[i] == C)
			return 0;
		if (v[i] == A) return 1;
	}
	return 0;
}

int isNextLightest(vector<int>& v, int A, int B, int C, int D)
{
	int lightest = 0;
	bool found = false;
	for (auto e : v)
	{
		if (e == D) found = true;
		else if (e == A || e == B || e == C)
		{
			if (found)
				return e;
			else if (lightest == 0)
				lightest = e;
		}
	}
	return lightest;
}

void orderCoins() 
{
    // Lets think about it
    // There are a total of 6! 
    // permutations of coin sizes

    // 6! = 720 
    // This looks very brute-forceable

	vector<int> perm(6);
	iota(perm.begin(), perm.end(), 1);

	vector<vector<int>> p;
	do {
		p.push_back(perm);
	} while (next_permutation(perm.begin(), perm.end()));

	vector<vector<int>> temp;

	while (p.size() > 1)
	{
		cerr << p.size() << '\n';

		// Heaviest queries
		int heavymx = 10000;
		tuple<int, int, int> heavyQ;
		for (int A = 1; A <= 6 - 2; A++)
		{
			for (int B = A + 1; B <= 6 - 1; B++)
			{
				for (int C = B + 1; C <= 6; C++)
				{
					int mx = 0;

					int cnt = 0;
					for (auto v : p)
					{
						if (isGreater(v, A, B, C))
							cnt++;
					}
					mx = max(cnt, mx);

					cnt = 0;
					for (auto v : p)
					{
						if (isGreater(v, B, A, C))
							cnt++;
					}
					mx = max(cnt, mx);

					cnt = 0;
					for (auto v : p)
					{
						if (isGreater(v, C, B, A))
							cnt++;
					}
					mx = max(cnt, mx);

					if (mx < heavymx)
					{
						heavymx = mx;
						heavyQ = {A, B, C};
					}
				}
			}
		}

		// Lightest queries
		int lightmx = 10000;
		tuple<int, int, int> lightQ;
		for (int A = 1; A <= 6 - 2; A++)
		{
			for (int B = A + 1; B <= 6 - 1; B++)
			{
				for (int C = B + 1; C <= 6; C++)
				{
					int mx = 0;

					int cnt = 0;
					for (auto v : p)
					{
						if (isLess(v, A, B, C))
							cnt++;
					}
					mx = max(cnt, mx);

					cnt = 0;
					for (auto v : p)
					{
						if (isLess(v, B, A, C))
							cnt++;
					}
					mx = max(cnt, mx);

					cnt = 0;
					for (auto v : p)
					{
						if (isLess(v, C, B, A))
							cnt++;
					}
					mx = max(cnt, mx);

					if (mx < lightmx)
					{
						lightmx = mx;
						lightQ = {A, B, C};
					}
				}
			}
		}

		// Next lightest queries
		int nlmx = 10000;
		tuple<int, int, int> nlQ;

		int nlD = 0;
		for (int A = 1; A <= 6 - 2; A++)
		{
			for (int B = A + 1; B <= 6 - 1; B++)
			{
				for (int C = B + 1; C <= 6; C++)
				{
					for (int D = 1; D <= 6; D++)
					{
						if (D == A || D == B || D == C)
							continue;

						int mx = 0;

						int cnt = 0;
						for (auto v : p)
						{
							if (isNextLightest(v, A, B, C, D) == A)
								cnt++;
						}
						mx = max(cnt, mx);

						cnt = 0;
						for (auto v : p)
						{
							if (isNextLightest(v, A, B, C, D) == B)
								cnt++;
						}
						mx = max(cnt, mx);

						cnt = 0;
						for (auto v : p)
						{
							if (isNextLightest(v, A, B, C, D) == C)
								cnt++;
						}
						mx = max(cnt, mx);

						if (mx < nlmx)
						{
							nlmx = mx;
							nlQ = {A, B, C};
							nlD = D;
						}
					}
				}
			}
		}

		int mnmx = min({heavymx, lightmx, nlmx});

		if (mnmx == heavymx)
		{
			int A, B, C;
			tie(A, B, C) = heavyQ;

			cerr << "getHeaviest(" << A << ", " << B << ", " << C << ") = ";
			int res = getHeaviest(A, B, C);
			cerr << res << '\n';

			temp.clear();
			if (res == A)
			{
				for (auto v : p)
				{
					if (isGreater(v, A, B, C))
						temp.push_back(v);
				}
			}
			else if (res == B)
			{
				for (auto v : p)
				{
					if (isGreater(v, B, A, C))
						temp.push_back(v);
				}
			}
			else if (res == C)
			{
				for (auto v : p)
				{
					if (isGreater(v, C, B, A))
						temp.push_back(v);
				}
			}
		}
		else if (mnmx == lightmx)
		{
			int A, B, C;
			tie(A, B, C) = lightQ;

			cerr << "getLightest(" << A << ", " << B << ", " << C << ") = ";
			int res = getLightest(A, B, C);
			cerr << res << '\n';


			temp.clear();
			if (res == A)
			{
				for (auto v : p)
				{
					if (isLess(v, A, B, C))
						temp.push_back(v);
				}
			}
			else if (res == B)
			{
				for (auto v : p)
				{
					if (isLess(v, B, A, C))
						temp.push_back(v);
				}
			}
			else if (res == C)
			{
				for (auto v : p)
				{
					if (isLess(v, C, B, A))
						temp.push_back(v);
				}
			}
		}
		else if (mnmx == nlmx)
		{
			int A, B, C, D;
			tie(A, B, C) = nlQ;
			D = nlD;

			cerr << "getNextLightest(" << A << ", " << B << ", " << C << ", " << D << ") = ";
			int res = getNextLightest(A, B, C, D);
			cerr << res << '\n';

			temp.clear();
			if (res == A)
			{
				for (auto v : p)
				{
					if (isNextLightest(v, A, B, C, D) == A)
						temp.push_back(v);
				}
			}
			else if (res == B)
			{
				for (auto v : p)
				{
					if (isNextLightest(v, A, B, C, D) == B)
						temp.push_back(v);
				}
			}
			else if (res == C)
			{
				for (auto v : p)
				{
					if (isNextLightest(v, A, B, C, D) == C)
						temp.push_back(v);
				}
			}
		}
		swap(p, temp);
	}

	int W[] = {p[0][0], p[0][1], p[0][2], p[0][3], p[0][4], p[0][5]}; 
	answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
    6 | void init(int T)
      |           ~~~~^

• Subtask 1: 71.428571 / 100