Submission #387920

#	Time	Username	Problem	Language	Result	Execution time	Memory
387920		Keshi	Scales (IOI15_scales)	C++17	71.73 / 100	24 ms	964 KiB

scales

//In the name of God
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;
typedef array<int, 6> perm;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define g1 getLightest
#define g2 getMedian
#define g3 getHeaviest
#define g4 getNextLightest

perm a[1000];
array<int, 3> b[100];
array<int, 4> c[100];
ll ans[1000][200];

namespace {
ll get1(perm p, ll a, ll b, ll c){
	ll t = 0;
	for(ll i = 0; i < 6; i++){
		if(p[i] == a || p[i] == b || p[i] == c) t++;
		if(t == 1) return p[i];
	}
	return 0;
}
ll get2(perm p, ll a, ll b, ll c){
	ll t = 0;
	for(ll i = 0; i < 6; i++){
		if(p[i] == a || p[i] == b || p[i] == c) t++;
		if(t == 2) return p[i];
	}
	return 0;
}
ll get3(perm p, ll a, ll b, ll c){
	ll t = 0;
	for(ll i = 0; i < 6; i++){
		if(p[i] == a || p[i] == b || p[i] == c) t++;
		if(t == 3) return p[i];
	}
	return 0;
}
ll get4(perm p, ll a, ll b, ll c, ll d){
	bool f = 0;
	for(ll i = 0; i < 6; i++){
		if(p[i] == d) f = 1;
		if(f && (p[i] == a || p[i] == b || p[i] == c)) return p[i];
	}
	return get1(p, a, b, c);
}
}
void init(int T){
	perm p;
	for(ll i = 0; i < 6; i++){
		p[i] = i + 1;
	}
	ll t = 0;
	do{
		a[t++] = p;
	}while(next_permutation(all(p)));
	for(ll i = 0; i < 6; i++){
		p[i] = ll(i > 2);
	}
	t = 0;
	ll t2 = 0;
	do{
		ll tt = 0;
		for(ll j = 0; j < 6; j++){
			if(p[j]) b[t][tt++] = j + 1;
		}
		array<int, 4> p2;
		for(ll i = 0; i < 3; i++){
			p2[i] = b[t][i];
		}
		for(ll i = 0; i < 6; i++){
			if(!p[i]){
				p2[3] = i + 1;
				c[t2++] = p2;
			}
		}
		t++;
	}while(next_permutation(all(p)));
	for(ll i = 0; i < 720; i++){
		for(ll j = 0; j < 20; j++){
			ans[i][j] = get1(a[i], b[j][0], b[j][1], b[j][2]);
		}
		for(ll j = 0; j < 20; j++){
			ans[i][j + 20] = get2(a[i], b[j][0], b[j][1], b[j][2]);
		}
		for(ll j = 0; j < 20; j++){
			ans[i][j + 40] = get3(a[i], b[j][0], b[j][1], b[j][2]);
		}
		for(ll j = 0; j < 60; j++){
			ans[i][j + 60] = get4(a[i], c[j][0], c[j][1], c[j][2], c[j][3]);
		}
	}
}

ll ok[1000];

void orderCoins(){
	fill(ok, ok + 720, 1);
	ll cnt[7];
  	ll rr = 720;
	while(rr > 1){
		ll q = -1, mn = inf;
		for(ll i = 0; i < 120; i++){
			fill(cnt, cnt + 7, 0);
			for(ll j = 0; j < 720; j++){
				if(ok[j]) cnt[ans[j][i]]++;
			}
			ll mx = 0;
			for(ll j = 0; j < 7; j++){
				mx = max(mx, cnt[j]);
			}
			if(mn > mx){
				mn = mx;
				q = i;
			}
		}
		ll x = 0;
		if(q < 20){
			x = g1(b[q % 20][0], b[q % 20][1], b[q % 20][2]);
		}
		else if(q < 40){
			x = g2(b[q % 20][0], b[q % 20][1], b[q % 20][2]);
		}
		else if(q < 60){
			x = g3(b[q % 20][0], b[q % 20][1], b[q % 20][2]);
		}
		else{
			x = g4(c[q - 60][0], c[q - 60][1], c[q - 60][2], c[q - 60][3]);
		}
		for(ll i = 0; i < 720; i++){
			if(ans[i][q] != x) ok[i] = 0;
		}
		rr = 0;
		for(ll i = 0; i < 720; i++){
			if(ok[i]) rr++;
		}
	}
	ll aa[6];
	for(ll i = 0; i < 720; i++){
		if(ok[i]){
			for(ll j = 0; j < 6; j++){
				aa[j] = a[i][j];
			}
			answer(aa);
			return;
		}
	}
	return;
}

/*int main(){

	init(0);

    return 0;
}*/

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:66:15: warning: unused parameter 'T' [-Wunused-parameter]
   66 | void init(int T){
      |           ~~~~^

• Subtask 1: 71.72619 / 100