Submission #764353

#	Time	Username	Problem	Language	Result	Execution time	Memory
764353		SanguineChameleon	Scales (IOI15_scales)	C++17	100 / 100	783 ms	624 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];
 
int solve(vector<vector<int>> cands, int rem) {
	if ((int)cands.size() <= 1) {
		return 120;
	}
	int lim = 1;
	for (int i = 0; i < rem - 1; i++) {
		lim *= 3;
	}
	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];
		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);
			}
		}
		if (candsA.empty() + candsB.empty() + candsC.empty() == 2) {
			continue;
		}
		if ((int)candsA.size() > lim || (int)candsB.size() > lim || (int)candsC.size() > lim) {
			continue;
		}
		if (solve(candsA, rem - 1) != -1 && solve(candsB, rem - 1) != 1 && solve(candsC, rem - 1) != -1) {
			return id;
		}
	}
	return -1;
}
 
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()));
	int rem = 6;
	while ((int)cands.size() > 1) {
		int id = solve(cands, rem);
		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) {
			cands.swap(candsA);
		}
		if (res == B) {
			cands.swap(candsB);
		}
		if (res == C) {
			cands.swap(candsC);
		}
		rem--;
	}
	perm = cands[0];
	for (int i = 0; i < 6; i++) {
		W[perm[i] - 1] = i + 1;
	}
	answer(W);
	return;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100