Submission #339106

#	Time	Username	Problem	Language	Result	Execution time	Memory
339106		LucaDantas	Scales (IOI15_scales)	C++17	100 / 100	63 ms	492 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define ff first
#define ss second

constexpr int maxn = 2020;

vector<vector<int>> perm;
vector<pair<int,vector<int>>> operacoes;

int cool[maxn], ended[maxn], pot[7];

bool solve(int pos, int steps, vector<int> possible) {
	if(sz(possible) <= 1) {
		if(sz(possible) == 1)
			cool[pos] = possible[0], ended[pos] = 1;
		return true;
	}
	for(int g = 0; g < sz(operacoes); g++) {
		auto op = operacoes[g];
		bool ok = 1;

		vector<int> ans[3];

		for(int p : possible) {
			int x = perm[p][op.ss[0]];
			int y = perm[p][op.ss[1]];
			int z = perm[p][op.ss[2]];
			int val[] = {x, y, z}, decode[6];
			sort(val, val+3);
			decode[x] = 0;
			decode[y] = 1;
			decode[z] = 2;

			if(op.ff == 1) ans[decode[val[0]]].pb(p);
			else if(op.ff == 2) ans[decode[val[1]]].pb(p);
			else if(op.ff == 3) ans[decode[val[2]]].pb(p);
			else {
				int w = perm[p][op.ss[3]];
				if(w > val[2] || w < val[0]) ans[decode[val[0]]].pb(p);
				else if(w < val[1]) ans[decode[val[1]]].pb(p);
				else ans[decode[val[2]]].pb(p);
			}
		}

		if(max({sz(ans[0]), sz(ans[1]), sz(ans[2])}) > pot[steps-1])
			continue;

		for(int i = 0; i < 3; i++) {
			ok &= solve(pos*3 + i, steps-1, ans[i]);
			if(!ok) continue;
		}

		if(ok) {
			cool[pos] = g;
			return true;
		}
	}
	return false;
}

void init(int T) {
	++T;
	pot[0] = 1;
	for(int i = 1; i < 7; i++)
		pot[i] = 3*pot[i-1];

	vector<int> pos(6);
	iota(pos.begin(), pos.end(), 0);
	do { 
		perm.pb(pos);
	} while(next_permutation(pos.begin(), pos.end()));

	for(int mask = 0; mask < (1 << 6); mask++) {
		if(__builtin_popcount(mask) != 3) continue;
		vector<int> ligados;
		for(int i = 0; i < 6; i++)
			if(mask&(1<<i)) ligados.pb(i);
		for(int i = 1; i < 4; i++)
			operacoes.pb({i, ligados});
		for(int i = 0; i < 6; i++) {
			if(!(mask&(1<<i))) {
				ligados.pb(i);
				operacoes.pb({4, ligados});
				ligados.pop_back();
			}
		}
	}

	vector<int> lista(720);
	iota(all(lista), 0);
	solve(1, 6, lista);
}

int get(int pos) {
	if(ended[pos]) return cool[pos];
	auto op = operacoes[cool[pos]];
	int ans;
	if(op.ff == 1) ans = getLightest(op.ss[0]+1, op.ss[1]+1, op.ss[2]+1);
	else if(op.ff == 2) ans = getMedian(op.ss[0]+1, op.ss[1]+1, op.ss[2]+1);
	else if(op.ff == 3) ans = getHeaviest(op.ss[0]+1, op.ss[1]+1, op.ss[2]+1);
	else ans = getNextLightest(op.ss[0]+1, op.ss[1]+1, op.ss[2]+1, op.ss[3]+1);
	for(int i = 0; i < 3; i++)
		if(op.ss[i]+1 == ans) return get(pos*3 + i);
	assert(0);
	return -1;
}

void orderCoins() {
	int pos = get(1);
	int W[6];
	for(int i = 0; i < 6; i++)
		W[perm[pos][i]] = i+1;
	answer(W);
}

• Subtask 1: 100 / 100