Submission #831885

#	Time	Username	Problem	Language	Result	Execution time	Memory
831885		Asymmetry	Scales (IOI15_scales)	C++17	71.73 / 100	300 ms	612 KiB

scales

#ifndef LOCAL
#include "scales.h"
#endif
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

// przyjmują wartościowanie
int applyLightest(vector<int> cur, int a, int b, int c) {
	vector<int> xd = {a, b, c};
	sort(xd.begin(), xd.end(), [&](int x, int y) {
			return cur[x] < cur[y];
			});
	return xd[0];
}

int applyMedian(vector<int> cur, int a, int b, int c) {
	vector<int> xd = {a, b, c};
	sort(xd.begin(), xd.end(), [&](int x, int y) {
			return cur[x] < cur[y];
			});
	return xd[1];
}

int applyHeaviest(vector<int> cur, int a, int b, int c) {
	vector<int> xd = {a, b, c};
	sort(xd.begin(), xd.end(), [&](int x, int y) {
			return cur[x] < cur[y];
			});
	return xd[2];
}

int applyNextLightest(vector<int> cur, int a, int b, int c, int d) {
	vector<int> xd = {a, b, c, d};
	sort(xd.begin(), xd.end(), [&](int x, int y) {
			return cur[x] < cur[y];
			});
	xd.emplace_back(xd[0]);
	REP (i, ssize(xd) - 1)
		if (xd[i] == d)
			return xd[i + 1];
	assert(false);
	return -1;
}

#ifdef LOCAL
int query_cnt;
vector<int> per;
int getLightest(int a, int b, int c) {
	++query_cnt;
	return applyLightest(per, a - 1, b - 1, c - 1) + 1;
}

int getMedian(int a, int b, int c) {
	++query_cnt;
	return applyMedian(per, a - 1, b - 1, c - 1) + 1;
}

int getHeaviest(int a, int b, int c) {
	++query_cnt;
	return applyHeaviest(per, a - 1, b - 1, c - 1) + 1;
}

int getNextLightest(int a, int b, int c, int d) {
	++query_cnt;
	return applyNextLightest(per, a - 1, b - 1, c - 1, d - 1) + 1;
}

void answer(int t[6]) {
	REP (i, 6)
		debug(i, t[i]);
	REP (i, 6)
		assert(1 <= t[i] && t[i] <= 6);
	REP (i, 5)
		assert(per[t[i] - 1] < per[t[i + 1] - 1]);
}
#endif

const int N = 6;
void init(int tests) {
	assert(tests);
}

void orderCoins() {
	mt19937 rng(12938721);
	auto rd = [&](int l, int r) {
		return int(rng() % (r - l + 1) + l);
	};
	auto apply_move = [&](vector<vector<int>> perms, tuple<int, int, int, int, int> move) {
		auto [type, a, b, c, d] = move;
		map<int, vector<vector<int>>> mp;
		for (auto v : perms) {
			if (type == 0)
				mp[applyLightest(v, a, b, c)].emplace_back(v);
			else if (type == 1)
				mp[applyMedian(v, a, b, c)].emplace_back(v);
			else if (type == 2)
				mp[applyHeaviest(v, a, b, c)].emplace_back(v);
			else
				mp[applyNextLightest(v, a, b, c, d)].emplace_back(v);
		}
		return tuple(mp[a], mp[b], mp[c]);
	};

	vector<vector<int>> cur_perms;
	vector<int> cur(N);
	iota(cur.begin(), cur.end(), 0);
	do {
		cur_perms.emplace_back(cur);
	} while (next_permutation(cur.begin(), cur.end()));
	while (ssize(cur_perms) > 1) {
		debug(ssize(cur_perms));
		debug(cur_perms);
		const int INF = int(1e9);
		tuple<int, int, int, int, int> best_move = tuple(0, 0, 0, 0, 0);
		int best_score = INF;
		const int reps = int(1e4) / ssize(cur_perms);
		REP (rep, reps) {
			if (rep % 10 == 0)
				debug(rep);
			int type = rd(0, 3);
			vector<int> tym(N);
			iota(tym.begin(), tym.end(), 0);
			shuffle(tym.begin(), tym.end(), rng);
			auto move = tuple(type, tym[0], tym[1], tym[2], tym[3]);
			auto [ra, rb, rc] = apply_move(cur_perms, move);
			int score = max({ssize(ra), ssize(rb), ssize(rc)});
			if (score < best_score) {
				best_score = score;
				best_move = move;
			}
		}


		auto [na, nb, nc] = apply_move(cur_perms, best_move);

		auto [type, a, b, c, d] = best_move;
		debug(na);
		debug(nb);
		debug(nc);
		debug(best_score);
		++a;
		++b;
		++c;
		++d;
		debug(type, a, b, c, d);
		int w;
		if (type == 0)
			w = getLightest(a, b, c);
		else if (type == 1)
			w = getMedian(a, b, c);
		else if (type == 2)
			w = getHeaviest(a, b, c);
		else
			w = getNextLightest(a, b, c, d);
		debug(w);
		if (w == a)
			cur_perms = na;
		else if (w == b)
			cur_perms = nb;
		else
			cur_perms = nc;
	}
	debug(cur_perms[0]);
	int ans[6];
	REP (i, 6)
		ans[cur_perms[0][i]] = i + 1;
	answer(ans);
}

#ifdef LOCAL
int main() {
	cin.tie(0)->sync_with_stdio(0);
	init(18);
	mt19937 main_rng(38182);
	per.resize(6);
	iota(per.begin(), per.end(), 0);
	REP (i, 18) {
		shuffle(per.begin(), per.end(), main_rng);
		debug(per);
		query_cnt = 0;
		orderCoins();
		cerr << "Asked_queries: " << query_cnt << endl;
	}
}
#endif

• Subtask 1: 71.72619 / 100