Submission #349560

#	Time	Username	Problem	Language	Result	Execution time	Memory
349560		pit4h	Scales (IOI15_scales)	C++14	100 / 100	409 ms	876 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
//#define cerr if(0)cerr
using namespace std;

int test_cases;
void init(int T) {
	test_cases = T;
}
vector<vector<int>> split(vector<vector<int>> permutations, vector<vector<int>> subpermutations) {
	vector<vector<int>> res;
	vector<bool> is_in(7);
	for(int i: subpermutations[0]) {
		is_in[i] = 1;
	}
	for(vector<int> p: permutations) {
		vector<int> q = {};
		for(int i: p) {
			if(is_in[i]) {
				q.push_back(i);
			}
		}
		bool found = 0;
		for(vector<int> sp: subpermutations) {
			if(q==sp) {
				found = 1;
				break;
			}
		}
		if(found) {
			res.push_back(p);
		}
	}
	return res;
}
vector<vector<int>> get_minimum(vector<int> p, int result) {
	swap(p[0], p[result]);
	vector<vector<int>> res = {{p[0], p[1], p[2]}, {p[0], p[2], p[1]}};
	return res;
}
vector<vector<int>> get_median(vector<int> p, int result) {
	swap(p[0], p[result]);
	vector<vector<int>> res = {{p[1], p[0], p[2]}, {p[2], p[0], p[1]}};
	return res;
}
vector<vector<int>> get_maximum(vector<int> p, int result) {
	swap(p[0], p[result]);
	vector<vector<int>> res = {{p[1], p[2], p[0]}, {p[2], p[1], p[0]}};
	return res;
}
vector<vector<int>> get_next(int i, vector<int> p, int result) {
	swap(p[0], p[result]);
	vector<vector<int>> res = {{i, p[0], p[1], p[2]}, {i, p[0], p[2], p[1]}, {p[1], i, p[0], p[2]}, {p[2], i, p[0], p[1]}, 
			{p[1], p[2], i, p[0]}, {p[2], p[1], i, p[0]}, {p[0], p[1], p[2], i}, {p[0], p[2], p[1], i}};
	return res;
}

bool solve(int iter, vector<vector<int>> permutations, vector<string> operations, bool ask, vector<int> not_queried);
int pow3[] = {1, 3, 9, 27, 81, 243, 729};
bool go(vector<string> operations, vector<vector<int>> permutations, int chosen, bool ask, vector<int> not_queried) {
	vector<string> new_oper = operations;
	new_oper.back() += '-', new_oper.back() += (char)(chosen+'0');
	return solve((int)new_oper.size()+1, permutations, new_oper, ask, not_queried);
}
bool step(vector<vector<int>> (*f)(vector<int>p, int result), vector<vector<int>> permutations, vector<int> perm, int nxt, vector<string> operations, int (*getM)(int A, int B, int C), bool ask, 
				vector<int> not_queried) {
	vector<vector<vector<int>>> res(3); res[0].clear(), res[1].clear(), res[2].clear();
	if(nxt==-1) {
		for(int i=0; i<3; ++i) {
			res[i] = split(permutations, f(perm, i));
		}
	}
	else {
		for(int i=0; i<3; ++i) {
			res[i] = split(permutations, get_next(nxt, perm, i));
		}
	}
	assert(res[0].size() + res[1].size() + res[2].size() == permutations.size());
	if( ( (int)max({res[0].size(), res[1].size(), res[2].size()}) <= 719 / pow3[(int)operations.size()] + 1) ) {
		bool ok = 1;
		for(int i=0; i<3; ++i) {
			vector<int> _not_queried = not_queried;
			for(int j=0; j<(int)_not_queried.size(); ++j) {
				if(_not_queried[j]==i) {
					_not_queried.erase(_not_queried.begin()+j);
					break;
				}
			}
			if(!go(operations, res[i], i, 0, _not_queried)) ok = 0;
		}
		if(ask && ok) {
			int ans;
			if(nxt!=-1) ans = getNextLightest(perm[0], perm[1], perm[2], nxt);
			else ans = getM(perm[0], perm[1], perm[2]);
			
			vector<int> _not_queried = not_queried;
			for(int i=0; i<(int)_not_queried.size(); ++i) {
				if(_not_queried[i]==ans) {
					_not_queried.erase(_not_queried.begin()+i);
					break;
				}
			}
			for(int i=0; i<3; ++i) { if(ans==perm[i]) {ans = i; break;} ;}
			
			go(operations, res[ans], ans, 1, _not_queried);
			return true;
		}
		return ok;
	}
	return false;
}
bool printed=0;
vector<int> ans_permutation = {1, 3, 2, 4, 5, 6};
bool solve(int iter, vector<vector<int>> permutations, vector<string> operations, bool ask, vector<int> not_queried) {
	if(iter==1) {
		vector<string> new_oper = operations;
		new_oper.push_back("123min");
		step(get_minimum, permutations, {1, 2, 3}, -1, new_oper, getLightest, ask, not_queried);
		return true;
	}
	if(iter==2) {
		vector<string> new_oper = operations;
		new_oper.push_back("456med");
		step(get_median, permutations, {4, 5, 6}, -1, new_oper, getMedian, ask, not_queried);
		return true;
	}
	if(iter==3) {
		vector<string> new_oper = operations;
		string txt; txt += (char)(not_queried[0]+'0'), txt += (char)(not_queried[2]+'0'), txt += (char)(not_queried[3]+'0'), txt += (char)(not_queried[1]+'0');
		new_oper.push_back(txt);
		int nxt = not_queried[1];
		not_queried.erase(not_queried.begin()+1);
		step(get_minimum, permutations, not_queried, nxt, new_oper, getLightest, ask, not_queried); 
		return true;
	}
	if(iter == 7) {
		if(ask) {
			int W[] = {1, 2, 3, 4, 5, 6};
			for(int i=0; i<6; ++i) W[i] = permutations[0][i];
			assert(permutations.size()==1);
			answer(W);
		}
		return true;
	}
	for(int i=1; i<=6; ++i) {
		for(int j=i+1; j<=6; ++j) {
			for(int k=j+1; k<=6; ++k) {
			
				vector<int> p = {i, j, k};
				
				vector<string> new_oper = operations;
				string txt = ""; txt += (char)(i+'0'), txt += (char)(j+'0'), txt += (char)(k+'0');
				new_oper.push_back(txt + "min");
				if(step(get_minimum, permutations, p, -1, new_oper, getLightest, 0, not_queried)) {
					if(ask) step(get_minimum, permutations, p, -1, new_oper, getLightest, 1, not_queried);
					return true;		
				}

				new_oper = operations;
				txt = ""; txt += (char)(i+'0'), txt += (char)(j+'0'), txt += (char)(k+'0');
				new_oper.push_back(txt + "med");
				if(step(get_median, permutations, p, -1, new_oper, getMedian, 0, not_queried)) {
					if(ask) step(get_median, permutations, p, -1, new_oper, getMedian, 1, not_queried);
					return true;
				}

				new_oper = operations;
				txt = ""; txt += (char)(i+'0'), txt += (char)(j+'0'), txt += (char)(k+'0');
				new_oper.push_back(txt + "max");
				if(step(get_maximum, permutations, p, -1, new_oper, getHeaviest, 0, not_queried)) {
					if(ask) step(get_maximum, permutations, p, -1, new_oper, getHeaviest, 1, not_queried);
					return true;
				}

				/*for(int l=1; l<=6; ++l) {
					if(l==i || l==j || l==k) continue;
					new_oper = operations;
					txt = ""; txt += (char)(i+'0'), txt += (char)(j+'0'), txt += (char)(k+'0'), txt += (char)(l+'0');
					new_oper.push_back(txt + "next");
					if(step(get_minimum, permutations, p, l, new_oper, getLightest))
						return;
				}*/			
			}
		}
	}
	return false;
}
void orderCoins() {
	vector<vector<int>> permutations;
	permutations.push_back({1, 2, 3, 4, 5, 6});
	vector<int> current = permutations[0];
	while(next_permutation(current.begin(), current.end())) {
		permutations.push_back(current);
	}
	vector<string> operations = {};
	vector<int> not_queried = {1, 2, 3, 4, 5, 6};
	solve(1, permutations, operations, 1, not_queried);
}

• Subtask 1: 100 / 100