Submission #1154780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154780		KickingKun	Scales (IOI15_scales)	C++20	71.43 / 100	11 ms	484 KiB

scales

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

vector <int> ve[720];
int pos[720][7];

const int N = 6;

void init(int T) {
	vector <int> p = {1, 2, 3, 4, 5, 6};
	for (int i = 0; i < 720; i++) {
		ve[i] = p;
		for (int j = 0; j < 6; j++) pos[i][p[j]] = j;
		next_permutation(p.begin(), p.end());
	}
}

int res;
void solve(vector <int> &candidate) {
//	cerr << candidate.size() << '\n';
	if (candidate.size() == 1) {
		res = candidate[0];
		return;
	}
	
	int mi[4] = {int(2e9), int(2e9), int(2e9), int(2e9)}; 
	vector <int> triple[4];
	for (int a = 1; a <= 6; a++)
		for (int b = a + 1; b <= 6; b++)
			for (int c = b + 1; c <= 6; c++) {
				// ask query 1: which is heaviest
				int cntA = 0, cntB = 0, cntC = 0;
				for (int id: candidate) {
					int tmp = max({pos[id][a], pos[id][b], pos[id][c]});
					if (tmp == pos[id][a]) ++cntA;
					if (tmp == pos[id][b]) ++cntB;
					if (tmp == pos[id][c]) ++cntC;
				}
				int worst = max({cntA, cntB, cntC});
				if (worst < mi[0]) mi[0] = worst, triple[0] = {a, b, c};
				
				// ask query 2: which is lightest
				cntA = 0, cntB = 0, cntC = 0;
				for (int id: candidate) {
					int tmp = min({pos[id][a], pos[id][b], pos[id][c]});
					if (tmp == pos[id][a]) ++cntA;
					if (tmp == pos[id][b]) ++cntB;
					if (tmp == pos[id][c]) ++cntC;
				}
				worst = max({cntA, cntB, cntC});
				if (worst < mi[1]) mi[1] = worst, triple[1] = {a, b, c};
				
				// ask query 3: which is median
				cntA = 0, cntB = 0, cntC = 0;
				for (int id: candidate) {
					int minn = min({pos[id][a], pos[id][b], pos[id][c]});
					int maxx = max({pos[id][a], pos[id][b], pos[id][c]});
					if (pos[id][a] != minn && pos[id][a] != maxx) ++cntA;
					if (pos[id][b] != minn && pos[id][b] != maxx) ++cntB;
					if (pos[id][c] != minn && pos[id][c] != maxx) ++cntC;
				}
				worst = max({cntA, cntB, cntC});
				if (worst < mi[2]) mi[2] = worst, triple[2] = {a, b, c};
			}
	
	// ask query 4: which is the lighest such that heavier d
	for (int a = 1; a <= 6; a++)
		for (int b = a + 1; b <= 6; 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 cntA = 0, cntB = 0, cntC = 0;
					for (int id: candidate) {
						int posd = pos[id][d], tmp = 2e9;
						if (pos[id][a] > posd) tmp = min(tmp, pos[id][a]);
						if (pos[id][b] > posd) tmp = min(tmp, pos[id][b]);
						if (pos[id][c] > posd) tmp = min(tmp, pos[id][c]);
						
						if (tmp == 2e9) 
							tmp = min({pos[id][a], pos[id][b], pos[id][c]});
						
						if (pos[id][a] == tmp) ++cntA;
						if (pos[id][b] == tmp) ++cntB;
						if (pos[id][c] == tmp) ++cntC;
					}
					int worst = max({cntA, cntB, cntC});
					if (worst < mi[3]) mi[3] = worst, triple[3] = {a, b, c, d};
				}
	
	int best = min({mi[0], mi[1], mi[2], mi[3]});
	vector <int> child;
	
	if (best == mi[0]) {
		int a = triple[0][0], b = triple[0][1], c = triple[0][2];
		int ans = getHeaviest(a, b, c);
		for (int id: candidate) {
			int tmp = max({pos[id][a], pos[id][b], pos[id][c]});
			if (tmp == pos[id][ans]) child.emplace_back(id);
		}
	}
	else if (best == mi[1]) {
		int a = triple[1][0], b = triple[1][1], c = triple[1][2];
		int ans = getLightest(a, b, c);
		for (int id: candidate) {
			int tmp = min({pos[id][a], pos[id][b], pos[id][c]});
			if (tmp == pos[id][ans]) child.emplace_back(id);
		}
	}
	else if (best == mi[2]) {
		int a = triple[2][0], b = triple[2][1], c = triple[2][2];
		int ans = getMedian(a, b, c);
		for (int id: candidate) {
			int minn = min({pos[id][a], pos[id][b], pos[id][c]});
			int maxx = max({pos[id][a], pos[id][b], pos[id][c]});
//			cerr << minn << ' ' << maxx << '\n';
			if (pos[id][ans] != minn && pos[id][ans] != maxx)
				child.emplace_back(id);
		}
	}
	else {
		int a = triple[3][0], b = triple[3][1], c = triple[3][2], d = triple[3][3];
		int ans = getNextLightest(a, b, c, d);
//		cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
		for (int id: candidate) {
			int posd = pos[id][d], tmp = 2e9;
			if (pos[id][a] > posd) tmp = min(tmp, pos[id][a]);
			if (pos[id][b] > posd) tmp = min(tmp, pos[id][b]);
			if (pos[id][c] > posd) tmp = min(tmp, pos[id][c]);
			
			if (tmp == 2e9) 
				tmp = min({pos[id][a], pos[id][b], pos[id][c]});
			if (pos[id][ans] == tmp) child.emplace_back(id);
		}
	}
	solve(child);
}

void orderCoins() {
    vector <int> candidate(720); 
	iota(candidate.begin(), candidate.end(), 0);
	
    solve(candidate);
    
	int ans[6] = {};
    for (int i = 0; i < 6; i++)
		ans[i] = ve[res][i];
	answer(ans);
}

• Subtask 1: 71.4286 / 100