Submission #831885

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831885	2023-08-20T16:49:49 Z	Asymmetry	Scales (IOI15_scales)	C++17	71.7262 / 100	300 ms	612 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	255 ms	480 KB	Output is partially correct
2	Partially correct	281 ms	504 KB	Output is partially correct
3	Partially correct	263 ms	480 KB	Output is partially correct
4	Partially correct	252 ms	488 KB	Output is partially correct
5	Partially correct	257 ms	480 KB	Output is partially correct
6	Partially correct	273 ms	484 KB	Output is partially correct
7	Partially correct	259 ms	612 KB	Output is partially correct
8	Partially correct	261 ms	492 KB	Output is partially correct
9	Partially correct	258 ms	484 KB	Output is partially correct
10	Partially correct	262 ms	488 KB	Output is partially correct
11	Partially correct	260 ms	468 KB	Output is partially correct
12	Partially correct	255 ms	484 KB	Output is partially correct
13	Partially correct	256 ms	480 KB	Output is partially correct
14	Partially correct	254 ms	484 KB	Output is partially correct
15	Partially correct	265 ms	476 KB	Output is partially correct
16	Partially correct	252 ms	484 KB	Output is partially correct
17	Partially correct	257 ms	480 KB	Output is partially correct
18	Partially correct	300 ms	484 KB	Output is partially correct
19	Partially correct	269 ms	488 KB	Output is partially correct
20	Partially correct	253 ms	480 KB	Output is partially correct
21	Partially correct	270 ms	480 KB	Output is partially correct
22	Partially correct	279 ms	468 KB	Output is partially correct
23	Partially correct	252 ms	468 KB	Output is partially correct
24	Partially correct	265 ms	464 KB	Output is partially correct
25	Partially correct	251 ms	476 KB	Output is partially correct
26	Partially correct	263 ms	488 KB	Output is partially correct
27	Partially correct	256 ms	472 KB	Output is partially correct
28	Partially correct	260 ms	488 KB	Output is partially correct
29	Partially correct	255 ms	480 KB	Output is partially correct
30	Partially correct	256 ms	488 KB	Output is partially correct
31	Partially correct	265 ms	480 KB	Output is partially correct
32	Partially correct	255 ms	472 KB	Output is partially correct
33	Partially correct	258 ms	484 KB	Output is partially correct
34	Partially correct	264 ms	492 KB	Output is partially correct
35	Partially correct	248 ms	468 KB	Output is partially correct
36	Correct	255 ms	480 KB	Output is correct
37	Partially correct	254 ms	464 KB	Output is partially correct
38	Partially correct	257 ms	484 KB	Output is partially correct
39	Partially correct	265 ms	600 KB	Output is partially correct
40	Partially correct	258 ms	484 KB	Output is partially correct