Submission #764264

#	Time	Username	Problem	Language	Result	Execution time	Memory
764264		SanguineChameleon	Scales (IOI15_scales)	C++17	72.92 / 100	128 ms	508 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
 
int getHeaviest(vector<int> W, int A, int B, int C) {
	int res = A;
	if (W[B - 1] > W[res - 1]) {
		res = B;
	}
	if (W[C - 1] > W[res - 1]) {
		res = C;
	}
	return res;
}
 
int getLightest(vector<int> W, int A, int B, int C) {
	int res = A;
	if (W[B - 1] < W[res - 1]) {
		res = B;
	}
	if (W[C - 1] < W[res - 1]) {
		res = C;
	}
	return res;
}
 
int getMedian(vector<int> W, int A, int B, int C) {
	return A + B + C - getLightest(W, A, B, C) - getHeaviest(W, A, B, C);
}
 
int getNextLightest(vector<int> W, int A, int B, int C, int D) {
	int res = -1;
	if (W[A - 1] > W[D - 1] && (res == -1 || W[A - 1] < W[res - 1])) {
		res = A;
	}
	if (W[B - 1] > W[D - 1] && (res == -1 || W[B - 1] < W[res - 1])) {
		res = B;
	}
	if (W[C - 1] > W[D - 1] && (res == -1 || W[C - 1] < W[res - 1])) {
		res = C;
	}
	if (res == -1) {
		return getLightest(W, A, B, C);
	}
	else {
		return res;
	}
}
 
int Q[120][5];
int W[6];
 
void solve(vector<vector<int>> cands) {
	if ((int)cands.size() == 1) {
		vector<int> perm = cands[0];
		for (int i = 0; i < 6; i++) {
			W[perm[i] - 1] = i + 1;
		}
		answer(W);
		return;
	}
	pair<int, int> best = make_pair((int)cands.size() + 1, 1);
	for (int id = 0; id < 120; id++) {
		int A = Q[id][0];
		int B = Q[id][1];
		int C = Q[id][2];
		int D = Q[id][3];
		int type = Q[id][4];
		int cntA = 0;
		int cntB = 0;
		int cntC = 0;
		for (auto cand: cands) {
			int res = -1;
			if (type == 1) {
				res = getHeaviest(cand, A, B, C);
			}
			if (type == 2) {
				res = getLightest(cand, A, B, C);
			}
			if (type == 3) {
				res = getMedian(cand, A, B, C);
			}
			if (type == 4) {
				res = getNextLightest(cand, A, B, C, D);
			}
			if (res == A) {
				cntA++;
			}
			if (res == B) {
				cntB++;
			}
			if (res == C) {
				cntC++;
			}
		}
		best = min(best, make_pair(max(max(cntA, cntB), cntC), -id));
	}
	int id = -best.second;
	int A = Q[id][0];
	int B = Q[id][1];
	int C = Q[id][2];
	int D = Q[id][3];
	int type = Q[id][4];
	vector<vector<int>> candsA, candsB, candsC;
	for (auto cand: cands) {
		int res = -1;
		if (type == 1) {
			res = getHeaviest(cand, A, B, C);
		}
		if (type == 2) {
			res = getLightest(cand, A, B, C);
		}
		if (type == 3) {
			res = getMedian(cand, A, B, C);
		}
		if (type == 4) {
			res = getNextLightest(cand, A, B, C, D);
		}
		if (res == A) {
			candsA.push_back(cand);
		}
		if (res == B) {
			candsB.push_back(cand);
		}
		if (res == C) {
			candsC.push_back(cand);
		}
	}
	int res = -1;
	if (type == 1) {
		res = getHeaviest(A, B, C);
	}
	if (type == 2) {
		res = getLightest(A, B, C);
	}
	if (type == 3) {
		res = getMedian(A, B, C);
	}
	if (type == 4) {
		res = getNextLightest(A, B, C, D);
	}
	if (res == A) {
		solve(candsA);
	}
	if (res == B) {
		solve(candsB);
	}
	if (res == C) {
		solve(candsC);
	}
}
 
void init(int T) {
	int cnt = 0;
	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 type = 1; type <= 3; type++) {
					Q[cnt][0] = A;
					Q[cnt][1] = B;
					Q[cnt][2] = C;
					Q[cnt][3] = -1;
					Q[cnt][4] = type;
					cnt++;
				}
			}
		}
	}
	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) {
						Q[cnt][0] = A;
						Q[cnt][1] = B;
						Q[cnt][2] = C;
						Q[cnt][3] = D;
						Q[cnt][4] = 4;
						cnt++;
					}
				}
			}
		}
	}
}
 
void orderCoins() {
	vector<vector<int>> cands;
	vector<int> perm(6);
	for (int i = 0; i < 6; i++) {
		perm[i] = i + 1;
	}
	do {
		cands.push_back(perm);
	}
	while (next_permutation(perm.begin(), perm.end()));
	solve(cands);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:153:15: warning: unused parameter 'T' [-Wunused-parameter]
  153 | void init(int T) {
      |           ~~~~^

• Subtask 1: 72.916667 / 100