Submission #1243009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243009		crispxx	Scales (IOI15_scales)	C++20	71.43 / 100	17 ms	520 KiB

scales

#include <bits/stdc++.h>

#include "scales.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

void init(int T) {
	
}

void orderCoins() {
	set<vector<int>> perms;
	
	vector<int> p(6);
	iota(all(p), 1);
	
	do {
		perms.emplace(p);
	} while(next_permutation(all(p)));
	
	set<ar<int, 3>> for_min, for_med, for_max;
	
	fill(all(p), 0);
	
	p[3] = p[4] = p[5] = 1;
	
	do {
		vector<int> a;
		for(int i = 0; i < 6; i++) {
			if(p[i]) {
				a.pb(i + 1);
			}
		}
		for_min.insert({a[0], a[1], a[2]});
		for_med.insert({a[0], a[1], a[2]});
		for_max.insert({a[0], a[1], a[2]});
	} while(next_permutation(all(p)));
	
	int cnta, cntb, cntc, inda, indb, indc, mx;
	
	while(perms.size() > 1) {
		
		ar<int, 5> best;
		
		best[0] = -1e9;
		
		for(auto &[A, B, C] : for_min) {
			cnta = cntb = cntc = 0;
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if(inda > min(indb, indc)) cnta++;
				if(indb > min(inda, indc)) cntb++;
				if(indc > min(inda, indb)) cntc++;
			}
			
			mx = min({cnta, cntb, cntc});
			
			if( chmax(best[0], mx) ) {
				best[1] = 0;
				best[2] = A;
				best[3] = B;
				best[4] = C;
			}
		}
		
		for(auto &[A, B, C] : for_med) {
			cnta = cntb = cntc = 0;
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if( !( min(indb, indc) < inda && inda < max(indb, indc) ) ) cnta++;
				if( !( min(inda, indc) < indb && indb < max(inda, indc) ) ) cntb++;
				if( !( min(inda, indb) < indc && indc < max(inda, indb) ) ) cntc++;
			}
			
			mx = min({cnta, cntb, cntc});
			
			if( chmax(best[0], mx) ) {
				best[1] = 1;
				best[2] = A;
				best[3] = B;
				best[4] = C;
			}
		}
		
		for(auto &[A, B, C] : for_max) {
			cnta = cntb = cntc = 0;
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if(inda < max(indb, indc)) cnta++;
				if(indb < max(inda, indc)) cntb++;
				if(indc < max(inda, indb)) cntc++;
			}
			
			mx = min({cnta, cntb, cntc});
			
			if( chmax(best[0], mx) ) {
				best[1] = 2;
				best[2] = A;
				best[3] = B;
				best[4] = C;
			}
		}
		
		vector<vector<int>> for_del;
		
		int A = best[2], B = best[3], C = best[4];
		
		if( best[1] == 0 ) { // for_min
			int ask = getLightest(A, B, C);
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if(inda > min(indb, indc) && ask == A) for_del.pb(perm);
				if(indb > min(inda, indc) && ask == B) for_del.pb(perm);
				if(indc > min(inda, indb) && ask == C) for_del.pb(perm);
			}
			
			for_min.erase({A, B, C});
		}
		
		if( best[1] == 1 ) { // for_med
			int ask = getMedian(A, B, C);
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if( !( min(indb, indc) < inda && inda < max(indb, indc) ) && ask == A ) for_del.pb(perm);
				if( !( min(inda, indc) < indb && indb < max(inda, indc) ) && ask == B ) for_del.pb(perm);
				if( !( min(inda, indb) < indc && indc < max(inda, indb) ) && ask == C ) for_del.pb(perm);
			}
			
			for_med.erase({A, B, C});
		}
		
		if( best[1] == 2 ) { // for_max
			int ask = getHeaviest(A, B, C);
			
			for(auto &perm : perms) {
				for(int i = 0; i < 6; i++) {
					if(perm[i] == A) inda = i;
					if(perm[i] == B) indb = i;
					if(perm[i] == C) indc = i;
				}
				if(inda < max(indb, indc) && ask == A) for_del.pb(perm);
				if(indb < max(inda, indc) && ask == B) for_del.pb(perm);
				if(indc < max(inda, indb) && ask == C) for_del.pb(perm);
			}
			
			for_max.erase({A, B, C});
		}
		
		for(auto &perm : for_del) perms.erase(perm);
	}
	
	assert(perms.size() == 1);
	
	int C[6];
	
	auto ans = *perms.begin();
	
	for(int i = 0; i < 6; i++) C[i] = ans[i];
	
	answer(C);
}

• Subtask 1: 71.4286 / 100