Submission #345481

#	Time	Username	Problem	Language	Result	Execution time	Memory
345481		pit4h	Scales (IOI15_scales)	C++14	71.43 / 100	19 ms	364 KiB

scales

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

int test_cases;
void init(int T) {
	test_cases = T;
}

int get_pos(int val, vector<int>& order) {
	for(int i=0; i<(int)order.size(); ++i) {
		if(val==order[i]) {
			return i;
		}
	}
	return -1;
}
vector<int> get_cand(vector<int>& order) {
	vector<int> cand;
	for(int i=4; i<=6; ++i) {
		if(get_pos(i, order)==-1) {
			cand.push_back(i);
		}
	}
	return cand;
}
void orderCoins() {
	int queries = 0;
    int W[] = {1, 2, 3, 4, 5, 6};
	vector<int> order;

	order.push_back(1);

	while(get_cand(order).size()) {
		vector<int> cand = get_cand(order);
		if((int)cand.size()<3 && get_pos(3, order)==-1) {
			cand.push_back(3);
		}
		if((int)cand.size()<3 && get_pos(2, order)==-1) {
			cand.push_back(2);
		}
		for(int i=1; i<=2; ++i) {
			if((int)cand.size()<3) {
				cand.push_back(order[i]);
			}
		}
		order.push_back( getNextLightest(cand[0], cand[1], cand[2], order.back()) );
		queries++;
	}
	
	if(get_pos(2, order)==-1) {
		int nxt = getNextLightest(order[0], order[1], order[2], 2);
		order.insert(order.begin()+get_pos(nxt, order), 2);		
		queries++;
	}
	if(get_pos(3, order)==-1) {
		int nxt = getNextLightest(order[0], order[1], order[2], 3);
		order.insert(order.begin()+get_pos(nxt, order), 3);
		queries++;
	}
	
	
	// find minimum
	int lightest = getLightest(order[0], order[2], order[3]);
	queries++;
	if(lightest==order[0]) {
		lightest = getLightest(order[0], order[4], order[5]);
		queries++;
	}
	else if(lightest==order[2]) {
		lightest = getLightest(order[2], order[0], order[1]);
		queries++;
	}
	int start = get_pos(lightest, order);
	for(int i=0; i<6; ++i) {
		W[i] = order[(start+i)%6];
	}
	assert(queries<=7);
    answer(W);
}

• Subtask 1: 71.428571 / 100