Submission #591644

#	Time	Username	Problem	Language	Result	Execution time	Memory
591644		Temmie	Scales (IOI15_scales)	C++17	100 / 100	83 ms	456 KiB

scales

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

struct Q {
	int t, v[4];
	Q() { }
	Q(int _t, int _v1, int _v2, int _v3, int _v4 = 0) {
		t = _t;
		v[0] = _v1;
		v[1] = _v2;
		v[2] = _v3;
		v[3] = _v4;
	}
	int ask() {
		switch (t) {
			case 0: return getHeaviest(v[0] + 1, v[1] + 1, v[2] + 1) - 1;
			case 1: return getLightest(v[0] + 1, v[1] + 1, v[2] + 1) - 1;
			case 2: return getMedian(v[0] + 1, v[1] + 1, v[2] + 1) - 1;
			default: return getNextLightest(v[0] + 1, v[1] + 1, v[2] + 1, v[3] + 1) - 1;
		};
	}
	friend std::ostream& operator << (std::ostream& stream, const Q& q) {
		stream << q.t << " " << q.v[0] << " " << q.v[1] << " " << q.v[2] << " " << q.v[3];
		return stream;
	}
};

std::vector <Q> ques;

std::vector <std::vector <int>> ords;

void init(int) {
	std::vector <int> ord(6);
	std::iota(ord.begin(), ord.end(), 0);
	do { ords.emplace_back(ord); } while (std::next_permutation(ord.begin(), ord.end()));
	for (int v1 = 0; v1 < 6; v1++) {
		for (int v2 = v1 + 1; v2 < 6; v2++) {
			for (int v3 = v2 + 1; v3 < 6; v3++) {
				ques.emplace_back(0, v1, v2, v3);
				ques.emplace_back(1, v1, v2, v3);
				ques.emplace_back(2, v1, v2, v3);
			}
		}
	}
	for (int v4 = 0; v4 < 6; v4++) {
		for (int v1 = 0; v1 < 6; v1++) {
			for (int v2 = v1 + 1; v2 < 6; v2++) {
				for (int v3 = v2 + 1; v3 < 6; v3++) {
					if (v4 != v1 && v4 != v2 && v4 != v3) {
						ques.emplace_back(3, v1, v2, v3, v4);
					}
				}
			}
		}
	}
}

int max(int x, int y, int z, int) {
	return std::max({ x, y, z });
}

int min(int x, int y, int z, int) {
	return std::min({ x, y, z });
}

int med(int x, int y, int z, int) {
	static int v[3];
	v[0] = x;
	v[1] = y;
	v[2] = z;
	std::sort(v, v + 3);
	return v[1];
}

int nli(int x, int y, int z, int w) {
	int val = std::min({ x > w ? x : (1 << 30), y > w ? y : (1 << 30), z > w ? z : (1 << 30) });
	return val == (1 << 30) ? std::min({ x, y, z }) : val;
}

std::vector <std::function <int (int, int, int, int)>> fns = { max, min, med, nli };

void orderCoins() {
	auto left = ords;
	while ((int) left.size() > 1) {
		Q q = ques[0];
		int best = 1 << 30;
		for (const Q& que : ques) {
			int v[3] = { 0, 0, 0 };
			for (const std::vector <int>& ord : left) {
				for (int i = 0; i < 3; i++) {
					v[i] += ord[que.v[i]] == fns[que.t](ord[que.v[0]], ord[que.v[1]], ord[que.v[2]], ord[que.v[3]]);
				}
			}
			int val = std::max({ v[0], v[1], v[2] });
			if (val <= best) {
				best = val;
				q = que;
			}
		}
		std::vector <std::vector <int>> keep;
		int val = q.ask();
		for (const std::vector <int>& ord : left) {
			if (ord[val] == fns[q.t](ord[q.v[0]], ord[q.v[1]], ord[q.v[2]], ord[q.v[3]])) {
				keep.emplace_back(ord);
			}
		}
		left = keep;
	}
	std::vector <int> inv(6);
	for (int i = 0; i < 6; i++) {
		inv[left[0][i]] = i + 1;
	}
	answer(inv.data());
}

• Subtask 1: 100 / 100