Submission #831883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831883	2023-08-20T16:47:26 Z	Asymmetry	Scales (IOI15_scales)	C++17	71.4286 / 100	459 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 = 100;
		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.428571 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	401 ms	484 KB	Output is partially correct
2	Partially correct	405 ms	488 KB	Output is partially correct
3	Partially correct	398 ms	484 KB	Output is partially correct
4	Partially correct	409 ms	612 KB	Output is partially correct
5	Partially correct	459 ms	484 KB	Output is partially correct
6	Partially correct	401 ms	588 KB	Output is partially correct
7	Partially correct	397 ms	484 KB	Output is partially correct
8	Partially correct	403 ms	496 KB	Output is partially correct
9	Partially correct	398 ms	476 KB	Output is partially correct
10	Partially correct	458 ms	608 KB	Output is partially correct
11	Partially correct	397 ms	484 KB	Output is partially correct
12	Partially correct	408 ms	480 KB	Output is partially correct
13	Partially correct	398 ms	492 KB	Output is partially correct
14	Partially correct	404 ms	488 KB	Output is partially correct
15	Partially correct	398 ms	468 KB	Output is partially correct
16	Partially correct	399 ms	468 KB	Output is partially correct
17	Partially correct	431 ms	468 KB	Output is partially correct
18	Partially correct	404 ms	480 KB	Output is partially correct
19	Partially correct	398 ms	484 KB	Output is partially correct
20	Partially correct	398 ms	468 KB	Output is partially correct
21	Partially correct	406 ms	480 KB	Output is partially correct
22	Partially correct	432 ms	484 KB	Output is partially correct
23	Partially correct	409 ms	476 KB	Output is partially correct
24	Partially correct	405 ms	488 KB	Output is partially correct
25	Partially correct	419 ms	468 KB	Output is partially correct
26	Partially correct	398 ms	488 KB	Output is partially correct
27	Partially correct	404 ms	488 KB	Output is partially correct
28	Partially correct	405 ms	484 KB	Output is partially correct
29	Partially correct	400 ms	588 KB	Output is partially correct
30	Partially correct	405 ms	480 KB	Output is partially correct
31	Partially correct	406 ms	468 KB	Output is partially correct
32	Partially correct	397 ms	484 KB	Output is partially correct
33	Partially correct	397 ms	596 KB	Output is partially correct
34	Partially correct	401 ms	468 KB	Output is partially correct
35	Partially correct	403 ms	592 KB	Output is partially correct
36	Partially correct	399 ms	480 KB	Output is partially correct
37	Partially correct	403 ms	604 KB	Output is partially correct
38	Partially correct	398 ms	484 KB	Output is partially correct
39	Partially correct	405 ms	600 KB	Output is partially correct
40	Partially correct	405 ms	476 KB	Output is partially correct