Submission #1034633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034633		fv3	Scales (IOI15_scales)	C++14	55.56 / 100	72 ms	520 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;
}

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};
					}
				}
			}
		}

		if (heavymx < lightmx)
		{
			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
		{
			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);
				}
			}
		}
		swap(p, temp);
	}

	for (auto e : p[0])
		cerr << e  << ' ';
	cerr << '\n'; 

	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: 55.555556 / 100