Submission #339043

#	Time	Username	Problem	Language	Result	Execution time	Memory
339043		LucaDantas	Scales (IOI15_scales)	C++17	0 / 100	52 ms	620 KiB

scales

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

#define pb push_back

int W[6], P[7];
// answer(W);

void init(int T) {
	/* ... */
	++T;
}

vector<vector<int>> check_med(int i, array<int,3> val, vector<vector<int>> pos) {
	vector<vector<int>> ans;
	if(i) swap(val[i], val[0]);
	for(vector<int>& v : pos) {
		for(int x = 0; x < 6; x++)
			P[v[x]] = x;
		if(P[val[0]] < max(P[val[1]], P[val[2]]) &&
			P[val[0]] > min(P[val[1]], P[val[2]]))
				ans.pb(v);
	}
	return ans;
}

vector<vector<int>> check_big(int i, array<int,3> val, vector<vector<int>> pos) {
	vector<vector<int>> ans;
	if(i) swap(val[i], val[0]);
	for(vector<int>& v : pos) {
		for(int x = 0; x < 6; x++)
			P[v[x]] = x;
		if(P[val[0]] > max(P[val[1]], P[val[2]]))
				ans.pb(v);
	}
	return ans;
}

vector<vector<int>> check_small(int i, array<int,3> val, vector<vector<int>> pos) {
	vector<vector<int>> ans;
	if(i) swap(val[i], val[0]);
	for(vector<int>& v : pos) {
		for(int x = 0; x < 6; x++)
			P[v[x]] = x;
		if(P[val[0]] < min(P[val[1]], P[val[2]]))
				ans.pb(v);
	}
	return ans;
}

vector<vector<int>> check_4(int i, int resp, array<int,4> val, vector<vector<int>> pos) {
	vector<vector<int>> ans;
	for(vector<int>& v : pos) {
		vector<int> ord;
		for(int x = 0; x < 6; x++)
			if(find(val.begin(), val.end(), v[x]) != val.end())
				ord.pb(v[x]);
		int p = (int)(find(ord.begin(), ord.end(), val[i]) - ord.begin());
		p = (p+1)%4;
		if(val[resp] == ord[p])
			ans.pb(v);
	}
	return ans;
}

void solve(vector<vector<int>> pos, int sz) {
	if(!sz) {
		for(int i = 0; i < 6; i++)
			W[i] = pos[0][i];
		answer(W);
		return;
	}
	for(int mask = 0; mask < (1<<6); mask++) {
		if(__builtin_popcount(mask) == 3) {
			array<int,3> val; int ptr = 0;
			for(int i = 0; i < 6; i++)
				if(mask&(1<<i)) val[ptr++] = i+1;
			// median
			bool ok = 1;
			for(int x : {0, 1, 2})
				if((int)check_med(x, val, pos).size() > sz)
					{ok = 0; break;}
			int tam = 0;
			for(int x : {0, 1, 2})
				tam += (int)check_med(x, val, pos).size();
			if(ok) {
				int opa = getMedian(val[0], val[1], val[2]);
				for(int x : {0, 1, 2})
					if(val[x] == opa) { opa = x; break; }
				solve(check_med(opa, val, pos), sz/3);
				return;
			}
			// greatest
			ok = 1;
			for(int x : {0, 1, 2})
				if((int)check_big(x, val, pos).size() > sz)
					{ok = 0; break;}
			if(ok) {
				int opa = getHeaviest(val[0], val[1], val[2]);
				for(int x : {0, 1, 2})
					if(val[x] == opa) { opa = x; break; }
				solve(check_big(opa, val, pos), sz/3);
				return;
			}
			// smallest
			ok = 1;
			for(int x : {0, 1, 2})
				if((int)check_small(x, val, pos).size() > sz)
					{ok = 0; break;}
			if(ok) {
				int opa = getLightest(val[0], val[1], val[2]);
				for(int x : {0, 1, 2})
					if(val[x] == opa) { opa = x; break; }
				solve(check_small(opa, val, pos), sz/3);
				return;
			}	
		}
		else if(__builtin_popcount(mask) == 4) {
			// check 4
			array<int,4> val; int ptr = 0;
			for(int i = 0; i < 6; i++)
				if(mask&(1<<i)) val[ptr++] = i+1;

			bool ok;
			for(int y : {0, 1, 2, 3}) {
				ok = 1;
				for(int x : {0, 1, 2, 3})
					if(x != y &&(int)check_4(y, x, val, pos).size() > sz)
						{ok = 0; break;}
				if(ok) {
					if(y) swap(val[0], val[y]);
					int opa = getNextLightest(val[1], val[2], val[3], val[0]);
					if(y) swap(val[0], val[y]);
					for(int x : {0, 1, 2, 3})
						if(val[x] == opa) { opa = x; break; }
					solve(check_4(y, opa, val, pos), sz/3);
					return;
				}
			}
		}
	}
}

void orderCoins() {
	vector<int> perm(6);
	iota(perm.begin(), perm.end(), 1);
	vector<vector<int>> pos;
	do { 
		pos.pb(perm);
	} while(next_permutation(perm.begin(), perm.end()));
	array<int,3> val, val2;
	val[0] = 1, val[1] = 2, val[2] = 3;
	val2[0] = 4, val2[1] = 5, val2[2] = 6;
	array<int, 4> val3;
	val3[0] = 1, val3[1] = 2, val3[2] = 3, val3[3] = 4;
	solve(pos, 243);
}

• Subtask 1: 0 / 100