Submission #1284613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284613		kustov_vadim_533	Scales (IOI15_scales)	C++20	100 / 100	178 ms	524 KiB

scales

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <map>
#include <random>
#include <bitset>
#include <stack>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>

#include "scales.h"

using namespace std;

typedef long long ll;

const int N = 6;
const int F = 720;

int p[F][N], q[F][N];

struct op {
	int a = 0, b = 0, c = 0, d = 0, t = -1;
	bitset<F> m[3];
};

vector<op> ops;

void init(int T) {
	vector<int> pr = { 0, 1, 2, 3, 4, 5 };
	
	for (int i = 0; i < F; ++i) {
		for (int j = 0; j < N; ++j) {
			p[i][j] = pr[j];
			q[i][p[i][j]] = j;
		}
		next_permutation(pr.begin(), pr.end());
	}

	op x;
	for (x.a = 0; x.a < N; ++x.a) {
		for (x.b = x.a + 1; x.b < N; ++x.b) {
			for (x.c = x.b + 1; x.c < N; ++x.c) {
				vector<int> v = { x.a, x.b, x.c };

				x.t = 0;				
				for (int r = 0; r < 3; ++r) {
					for (int i = 0; i < F; ++i) {
						x.m[r][i] = (q[i][v[r]] >= q[i][x.a] && q[i][v[r]] >= q[i][x.b] && q[i][v[r]] >= q[i][x.c]);
					}
				}
				ops.push_back(x);

				x.t = 1;
				for (int r = 0; r < 3; ++r) {
					for (int i = 0; i < F; ++i) {
						x.m[r][i] = (q[i][v[r]] <= q[i][x.a] && q[i][v[r]] <= q[i][x.b] && q[i][v[r]] <= q[i][x.c]);
					}
				}
				ops.push_back(x);

				x.t = 2;
				for (int r = 0; r < 3; ++r) {
					for (int i = 0; i < F; ++i) {
						x.m[r][i] = !(q[i][v[r]] >= q[i][x.a] && q[i][v[r]] >= q[i][x.b] && q[i][v[r]] >= q[i][x.c]) && !(q[i][v[r]] <= q[i][x.a] && q[i][v[r]] <= q[i][x.b] && q[i][v[r]] <= q[i][x.c]);
					}
				}
				ops.push_back(x);

				for (x.d = x.c + 1; x.d < N; ++x.d) {
					x.t = 3;
					for (int i = 0; i < F; ++i) {
						int res = -1;
						
						if (q[i][x.a] > q[i][x.d]) {
							if (res == -1 || q[i][v[res]] > q[i][x.a]) {
								res = 0;
							}
						}
						if (q[i][x.b] > q[i][x.d]) {
							if (res == -1 || q[i][v[res]] > q[i][x.b]) {
								res = 1;
							}
						}
						if (q[i][x.c] > q[i][x.d]) {
							if (res == -1 || q[i][v[res]] > q[i][x.c]) {
								res = 2;
							}
						}

						if (res == -1) {
							for (int r = 0; r < 3; ++r) {
								x.m[r][i] = (q[i][v[r]] <= q[i][x.a] && q[i][v[r]] <= q[i][x.b] && q[i][v[r]] <= q[i][x.c]);

							}
						}
						else {
							for (int r = 0; r < 3; ++r) {
								x.m[r][i] = (r == res);
							}
						}
					}
					ops.push_back(x);
				}
			}
		}
	}
}

void orderCoins() {
	bitset<F> cur;
	for (int i = 0; i < F; ++i) {
		cur[i] = true;
	}

	while (cur.count() > 1) {
		int bs = 0;
		int rs = cur.count();

		for (int i = 0; i < ops.size(); ++i) {
			int res = 0;
			for (int ri = 0; ri < 3; ++ri) {
				res = max(res, (int)(cur & ops[i].m[ri]).count());
			}
			if (res < rs) {
				rs = res;
				bs = i;
			}
		}

		for (int i = 0; i < ops.size(); ++i) {
			int res = 0;
			for (int ri = 0; ri < 3; ++ri) {
				int res1 = F;
				for (int j = 0; j < ops.size(); ++j) {
					int res2 = 0;
					for (int rj = 0; rj < 3; ++rj) {
						res2 = max(res2, (int)(cur & ops[i].m[ri] & ops[j].m[rj]).count());
					}
					res1 = min(res1, res2);
				}
				res = max(res, res1);
			}
			if (res < rs) {
				rs = res;
				bs = i;
			}
		}

		op ch = ops[bs];

		if (ch.t == 0) {
			int r = getHeaviest(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
			if (r == ch.a) r = 0;
			else if (r == ch.b) r = 1;
			else r = 2;

			cur &= ch.m[r];
		}
		else if (ch.t == 1) {
			int r = getLightest(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
			if (r == ch.a) r = 0;
			else if (r == ch.b) r = 1;
			else r = 2;

			cur &= ch.m[r];
		}
		else if (ch.t == 2) {
			int r = getMedian(ch.a + 1, ch.b + 1, ch.c + 1) - 1;
			if (r == ch.a) r = 0;
			else if (r == ch.b) r = 1;
			else r = 2;

			cur &= ch.m[r];
		}
		else if (ch.t == 3) {
			int r = getNextLightest(ch.a + 1, ch.b + 1, ch.c + 1, ch.d + 1) - 1;
			if (r == ch.a) r = 0;
			else if (r == ch.b) r = 1;
			else r = 2;

			cur &= ch.m[r];
		}
	}

	int ans[N];
	for (int i = 0; i < F; ++i) {
		if (cur[i]) {
			for (int j = 0; j < N; ++j) {
				ans[j] = p[i][j] + 1;
			}
		}
	}
	answer(ans);
}

• Subtask 1: 100 / 100