Submission #1255527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255527		testaccount	Scales (IOI15_scales)	C++20	100 / 100	38 ms	512 KiB

scales

#include "scales.h"
#include "bits/stdc++.h"
using namespace std;
#define ALL(x) (x.begin()), (x.end())
#define RALL(x) (x.rbegin()), (x.rend())
#define SZ(x) ((int)x.size())
#define fi first
#define se second
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef array<int, 5> arr5;

vvi perm;
vector<array<int, 6>> permPos(720);
int pow3[7];
void init(int T) {
	pow3[0] = 1;
	for (int i = 1; i < 7; i++) pow3[i] = pow3[i-1]*3; 
	vi p = {0, 1, 2, 3, 4, 5};
	do { perm.push_back(p); } while(next_permutation(ALL(p)));
	for (int i = 0; i < 720; i++) {
		for (int j = 0; j < 6; j++) {
			permPos[i][perm[i][j]] = j;
		}
	}
	
}

vvi split(vi &alive, arr5 q) {
	auto [op, a, b, c, d] = q;
	vvi ret(3);
	for (int p : alive) {
		vector<pii> v = {
			{permPos[p][a], a},
			{permPos[p][b], b},
			{permPos[p][c], c}
		};
		sort(ALL(v));
		int idx = 0;
		if (op == 0) idx = (v[0].se == a) ? 0 : ((v[0].se == b) ? 1 : 2);
		if (op == 1) idx = (v[1].se == a) ? 0 : ((v[1].se == b) ? 1 : 2);
		if (op == 2) idx = (v[2].se == a) ? 0 : ((v[2].se == b) ? 1 : 2);
		if (op == 3) {
			int posa = permPos[p][a];
			int posb = permPos[p][b];
			int posc = permPos[p][c];
			int posd = permPos[p][d];
			vector<pii> v2;
			if (posa > posd) v2.push_back({posa, a});
			if (posb > posd) v2.push_back({posb, b});
			if (posc > posd) v2.push_back({posc, c});
			sort(ALL(v2));
			if (SZ(v2)) idx = (v2[0].se == a) ? 0 : ((v2[0].se == b) ? 1 : 2);
			else idx = (v[0].se == a) ? 0 : ((v[0].se == b) ? 1 : 2);
		}
		ret[idx].push_back(p);
	}
	return ret;
}

map<vi, arr5> dp;
arr5 solve(vi alive, int depth) {
	if (dp.find(alive) != dp.end()) return dp[alive];
	if (depth == 0) return (alive.size() <= 1) ? arr5{0} : arr5{-1};
	if (SZ(alive) > pow3[depth]) return {-1};
	vector<pair<int, arr5>> possible;
	for (int op = 0; op < 4; op++) {
		for (int a = 0; a < 6; a++) {
			for (int b = a+1; b < 6; b++) {
				for (int c = b+1; c < 6; c++) {
					if (op < 3) {
						int mx = 0;
						vvi sp = split(alive, {op, a, b, c, -1});
						for (int i = 0; i < 3; i++) mx = max(mx, SZ(sp[i]));
						if (mx <= pow3[depth-1]) possible.push_back({mx, {op, a, b, c, -1}});
					}
					else {
						for (int d = 0; d < 6; d++) if (d != a && d != b && d != c) {
							int mx = 0;
							vvi sp = split(alive, {op, a, b, c, d});
							for (int i = 0; i < 3; i++) mx = max(mx, SZ(sp[i]));
							if (mx <= pow3[depth-1]) possible.push_back({mx, {op, a, b, c, d}});
						}
					}
				}
			}
		}
	}
	sort(ALL(possible));
	for (auto [mx, q] : possible) {
		vvi sp = split(alive, q);
		bool ok = 1;
		for (int i = 0; i < 3; i++) {
			if (solve(sp[i], depth-1)[0] == -1) {
				ok = 0;
				break;
			}
		}
		if (ok) return dp[alive] = q;
	}
	return {-1};
}

void orderCoins() {
	vi alive(720);
	for (int i = 0; i < 720; i++) alive[i] = i;
	solve(alive, 6);
	int depth = 6;
	while (SZ(alive) > 1) {
		arr5 q = solve(alive, depth);
		auto [op, a, b, c, d] = q;
		a++, b++, c++, d++;
		int res = 0;
		if (op == 0) res = getLightest(a, b, c);
		if (op == 1) res = getMedian(a, b, c);
		if (op == 2) res = getHeaviest(a, b, c);
		if (op == 3) res = getNextLightest(a, b, c, d);
		vvi sp = split(alive, q);
		res = (res == a) ? 0 : ((res == b) ? 1 : 2);
		alive = sp[res];
		depth--;
	}
	int ans[6] = {0};
	for (int i = 0; i < 6; i++) ans[i] = perm[alive[0]][i]+1;
	//for (int i = 0; i < 6; i++) cout << ans[i] << " "; cout << endl;
	answer(ans);
}

• Subtask 1: 100 / 100