Submission #1243063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243063		crispxx	Scales (IOI15_scales)	C++20	Compilation error	0 ms	0 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array

vector<ar<int, 3>> for_min, for_med, for_max;
vector<ar<int, 4>> for_next_max;
vector<ar<int, 6>> perms;

void init() {
	for (int i = 0; i < 6; ++i)
		for (int j = 0; j < 6; ++j) if (j != i)
			for (int k = 0; k < 6; ++k) if (k != i && k != j)
				for_min.push_back({i, j, k});

	for (int i = 0; i < 6; ++i)
		for (int j = 0; j < 6; ++j) if (j != i)
			for (int k = 0; k < 6; ++k) if (k != i && k != j)
				for_med.push_back({i, j, k});

	for (int i = 0; i < 6; ++i)
		for (int j = 0; j < 6; ++j) if (j != i)
			for (int k = 0; k < 6; ++k) if (k != i && k != j)
				for_max.push_back({i, j, k});

	for (int i = 0; i < 6; ++i)
		for (int j = 0; j < 6; ++j) if (j != i)
			for (int k = 0; k < 6; ++k) if (k != i && k != j)
				for (int l = 0; l < 6; ++l) if (l != i && l != j && l != k)
					for_next_max.push_back({i, j, k, l});

	array<int, 6> p = {0, 1, 2, 3, 4, 5};
	do perms.push_back(p);
	while (next_permutation(p.begin(), p.end()));
}

int expected_lightest(int a, int b, int c, const ar<int, 6> &perm) {
	vector<pair<int, int>> pos = {{find(perm.begin(), perm.end(), a) - perm.begin(), a},
								   {find(perm.begin(), perm.end(), b) - perm.begin(), b},
								   {find(perm.begin(), perm.end(), c) - perm.begin(), c}};
	sort(pos.begin(), pos.end());
	return pos[0].second;
}

int expected_median(int a, int b, int c, const ar<int, 6> &perm) {
	vector<pair<int, int>> pos = {{find(perm.begin(), perm.end(), a) - perm.begin(), a},
								   {find(perm.begin(), perm.end(), b) - perm.begin(), b},
								   {find(perm.begin(), perm.end(), c) - perm.begin(), c}};
	sort(pos.begin(), pos.end());
	return pos[1].second;
}

int expected_heaviest(int a, int b, int c, const ar<int, 6> &perm) {
	vector<pair<int, int>> pos = {{find(perm.begin(), perm.end(), a) - perm.begin(), a},
								   {find(perm.begin(), perm.end(), b) - perm.begin(), b},
								   {find(perm.begin(), perm.end(), c) - perm.begin(), c}};
	sort(pos.begin(), pos.end());
	return pos[2].second;
}

int expected_next_lightest(int a, int b, int c, int d, const ar<int, 6> &perm) {
	vector<pair<int, int>> pos = {{find(perm.begin(), perm.end(), a) - perm.begin(), a},
								   {find(perm.begin(), perm.end(), b) - perm.begin(), b},
								   {find(perm.begin(), perm.end(), c) - perm.begin(), c},
								   {find(perm.begin(), perm.end(), d) - perm.begin(), d}};
	sort(pos.begin(), pos.end());
	return pos[1].second;
}

void orderCoins() {
	init();
	while (true) {
		if (perms.size() <= 5) {
			for (auto &perm : perms) {
				bool ok = true;
				ok &= (getLightest(perm[0], perm[1], perm[2]) == expected_lightest(perm[0], perm[1], perm[2], perm));
				ok &= (getMedian(perm[1], perm[2], perm[3]) == expected_median(perm[1], perm[2], perm[3], perm));
				ok &= (getHeaviest(perm[2], perm[3], perm[4]) == expected_heaviest(perm[2], perm[3], perm[4], perm));
				ok &= (getNextLightest(perm[1], perm[2], perm[3], perm[4]) == expected_next_lightest(perm[1], perm[2], perm[3], perm[4], perm));
				if (ok) {
					answer(perm.data());
					return;
				}
			}
		}

		array<int, 3> best = {-1, -1, -1};
		for (int i = 0; i < for_min.size(); ++i) {
			auto [a, b, c] = for_min[i];
			int cnta = 0, cntb = 0, cntc = 0;
			for (auto &perm : perms) {
				int inda = find(perm.begin(), perm.end(), a) - perm.begin();
				int indb = find(perm.begin(), perm.end(), b) - perm.begin();
				int indc = find(perm.begin(), perm.end(), c) - perm.begin();
				int mn = min({inda, indb, indc});
				if (inda == mn) cnta++;
				if (indb == mn) cntb++;
				if (indc == mn) cntc++;
			}
			int mx = max({cnta, cntb, cntc});
			if (mx > best[0]) best = {mx, 0, i};
		}

		for (int i = 0; i < for_med.size(); ++i) {
			auto [a, b, c] = for_med[i];
			int cnta = 0, cntb = 0, cntc = 0;
			for (auto &perm : perms) {
				vector<int> inds = {
					find(perm.begin(), perm.end(), a) - perm.begin(),
					find(perm.begin(), perm.end(), b) - perm.begin(),
					find(perm.begin(), perm.end(), c) - perm.begin()};
				sort(inds.begin(), inds.end());
				int med = inds[1];
				if (find(perm.begin(), perm.end(), a) - perm.begin() == med) cnta++;
				if (find(perm.begin(), perm.end(), b) - perm.begin() == med) cntb++;
				if (find(perm.begin(), perm.end(), c) - perm.begin() == med) cntc++;
			}
			int mx = max({cnta, cntb, cntc});
			if (mx > best[0]) best = {mx, 1, i};
		}

		for (int i = 0; i < for_max.size(); ++i) {
			auto [a, b, c] = for_max[i];
			int cnta = 0, cntb = 0, cntc = 0;
			for (auto &perm : perms) {
				int inda = find(perm.begin(), perm.end(), a) - perm.begin();
				int indb = find(perm.begin(), perm.end(), b) - perm.begin();
				int indc = find(perm.begin(), perm.end(), c) - perm.begin();
				int mx = max({inda, indb, indc});
				if (inda == mx) cnta++;
				if (indb == mx) cntb++;
				if (indc == mx) cntc++;
			}
			int mx = max({cnta, cntb, cntc});
			if (mx > best[0]) best = {mx, 2, i};
		}

		for (int i = 0; i < for_next_max.size(); ++i) {
			auto [a, b, c, d] = for_next_max[i];
			int cnts[4] = {};
			for (auto &perm : perms) {
				vector<pair<int, int>> pos = {
					{find(perm.begin(), perm.end(), a) - perm.begin(), a},
					{find(perm.begin(), perm.end(), b) - perm.begin(), b},
					{find(perm.begin(), perm.end(), c) - perm.begin(), c},
					{find(perm.begin(), perm.end(), d) - perm.begin(), d}};
				sort(pos.begin(), pos.end());
				for (int j = 0; j < 4; ++j) if (pos[1].second == pos[j].second) cnts[j]++;
			}
			int mx = *max_element(cnts, cnts + 4);
			if (mx > best[0]) best = {mx, 3, i};
		}

		vector<ar<int, 6>> new_perms;
		if (best[1] == 0) {
			auto [a, b, c] = for_min[best[2]];
			int res = getLightest(a, b, c);
			for (auto &perm : perms) {
				int inda = find(perm.begin(), perm.end(), a) - perm.begin();
				int indb = find(perm.begin(), perm.end(), b) - perm.begin();
				int indc = find(perm.begin(), perm.end(), c) - perm.begin();
				int mn = min({inda, indb, indc});
				if ((res == a && inda == mn) || (res == b && indb == mn) || (res == c && indc == mn))
					new_perms.push_back(perm);
			}
			for_min.erase(for_min.begin() + best[2]);
		}
		else if (best[1] == 1) {
			auto [a, b, c] = for_med[best[2]];
			int res = getMedian(a, b, c);
			for (auto &perm : perms) {
				vector<pair<int, int>> pos = {
					{find(perm.begin(), perm.end(), a) - perm.begin(), a},
					{find(perm.begin(), perm.end(), b) - perm.begin(), b},
					{find(perm.begin(), perm.end(), c) - perm.begin(), c}};
				sort(pos.begin(), pos.end());
				if (pos[1].second == res) new_perms.push_back(perm);
			}
			for_med.erase(for_med.begin() + best[2]);
		}
		else if (best[1] == 2) {
			auto [a, b, c] = for_max[best[2]];
			int res = getHeaviest(a, b, c);
			for (auto &perm : perms) {
				int inda = find(perm.begin(), perm.end(), a) - perm.begin();
				int indb = find(perm.begin(), perm.end(), b) - perm.begin();
				int indc = find(perm.begin(), perm.end(), c) - perm.begin();
				int mx = max({inda, indb, indc});
				if ((res == a && inda == mx) || (res == b && indb == mx) || (res == c && indc == mx))
					new_perms.push_back(perm);
			}
			for_max.erase(for_max.begin() + best[2]);
		}
		else if (best[1] == 3) {
			auto [a, b, c, d] = for_next_max[best[2]];
			int res = getNextLightest(a, b, c, d);
			for (auto &perm : perms) {
				vector<pair<int, int>> pos = {
					{find(perm.begin(), perm.end(), a) - perm.begin(), a},
					{find(perm.begin(), perm.end(), b) - perm.begin(), b},
					{find(perm.begin(), perm.end(), c) - perm.begin(), c},
					{find(perm.begin(), perm.end(), d) - perm.begin(), d}};
				sort(pos.begin(), pos.end());
				if (pos[1].second == res)
					new_perms.push_back(perm);
			}
			for_next_max.erase(for_next_max.begin() + best[2]);
		}
		perms = move(new_perms);
	}
}

Compilation message (stderr)

scales.cpp: In function 'void orderCoins()':
scales.cpp:110:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& a))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
  110 |                                         find(perm.begin(), perm.end(), a) - perm.begin(),
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:110:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& a))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
scales.cpp:111:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& b))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
  111 |                                         find(perm.begin(), perm.end(), b) - perm.begin(),
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:111:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& b))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
scales.cpp:112:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& c))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
  112 |                                         find(perm.begin(), perm.end(), c) - perm.begin()};
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:112:75: warning: narrowing conversion of '((std::find<int*, int>((& perm)->std::array<int, 6>::begin(), (& perm)->std::array<int, 6>::end(), (*(const int*)(& c))) - (& perm)->std::array<int, 6>::begin()) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
/usr/bin/ld: /tmp/ccLVujhL.o: in function `main':
grader.c:(.text.startup+0x83): undefined reference to `init'
collect2: error: ld returned 1 exit status