답안 #591644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591644	2022-07-07T17:22:28 Z	Temmie	저울 (IOI15_scales)	C++17	100 / 100	83 ms	456 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	392 KB	Output is correct
2	Correct	61 ms	340 KB	Output is correct
3	Correct	60 ms	384 KB	Output is correct
4	Correct	65 ms	340 KB	Output is correct
5	Correct	73 ms	340 KB	Output is correct
6	Correct	60 ms	396 KB	Output is correct
7	Correct	61 ms	392 KB	Output is correct
8	Correct	62 ms	388 KB	Output is correct
9	Correct	65 ms	388 KB	Output is correct
10	Correct	66 ms	396 KB	Output is correct
11	Correct	66 ms	384 KB	Output is correct
12	Correct	61 ms	384 KB	Output is correct
13	Correct	60 ms	400 KB	Output is correct
14	Correct	60 ms	340 KB	Output is correct
15	Correct	65 ms	388 KB	Output is correct
16	Correct	66 ms	400 KB	Output is correct
17	Correct	59 ms	340 KB	Output is correct
18	Correct	61 ms	340 KB	Output is correct
19	Correct	61 ms	400 KB	Output is correct
20	Correct	60 ms	388 KB	Output is correct
21	Correct	67 ms	396 KB	Output is correct
22	Correct	83 ms	300 KB	Output is correct
23	Correct	69 ms	404 KB	Output is correct
24	Correct	60 ms	388 KB	Output is correct
25	Correct	61 ms	388 KB	Output is correct
26	Correct	67 ms	456 KB	Output is correct
27	Correct	68 ms	388 KB	Output is correct
28	Correct	61 ms	388 KB	Output is correct
29	Correct	60 ms	404 KB	Output is correct
30	Correct	60 ms	392 KB	Output is correct
31	Correct	60 ms	340 KB	Output is correct
32	Correct	69 ms	340 KB	Output is correct
33	Correct	65 ms	392 KB	Output is correct
34	Correct	60 ms	340 KB	Output is correct
35	Correct	62 ms	296 KB	Output is correct
36	Correct	63 ms	388 KB	Output is correct
37	Correct	69 ms	384 KB	Output is correct
38	Correct	69 ms	388 KB	Output is correct
39	Correct	63 ms	400 KB	Output is correct
40	Correct	60 ms	340 KB	Output is correct