Submission #1075964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075964		Elias	Scales (IOI15_scales)	C++17	56.77 / 100	1 ms	600 KiB

scales

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
void init(int T);
void orderCoins();
void answer(int C[]);

int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
#else
#include "scales.h"
#endif

void init(int T) {}

int excl(vector<int> a, vector<int> b)
{
	for (int x : a)
	{
		bool found = false;
		for (int y : b)
			found |= x == y;
		if (!found)
			return x;
	}

	assert(false);
	return -1;
}

vector<int> order;

// void insert(int l, int r, int x)
// {
// 	if (l + 1 == r)
// 	{
// 		int median = getMedian(x, order[l], order[r]);
// 		if (median == order[l])
// 			order.insert(order.begin() + l, x);
// 		else if (median == order[r])
// 			order.insert(order.begin() + r + 1, x);
// 		else
// 			order.insert(order.begin() + r, x);
// 	}
// 	else if (l + 2 == r)
// 	{
// 		int median = getMedian(x, order[l], order[r]);
// 		if (median == order[l])
// 			order.insert(order.begin() + l, x);
// 		else if (median == order[r])
// 			order.insert(order.begin() + r + 1, x);
// 		else
// 			insert(l, r - 1, x);
// 	}
// 	else
// 	{
// 		int median = getMedian(x, order[l], order[r]);
// 		if (median == order[l])
// 			order.insert(order.begin() + l, x);
// 		else if (median == order[r])
// 			order.insert(order.begin() + r + 1, x);
// 		else
// 			insert(l + 1, r - 1, x);
// 	}
// }

void orderCoins()
{
	vector<int> shuf = {1, 2, 3, 4, 5, 6};
	srand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
	random_shuffle(shuf.begin(), shuf.end());
	shuf.insert(shuf.begin(), 0);

	vector<int> order1, order2;

	{
		int smallest = getLightest(shuf[1], shuf[2], shuf[3]);
		int biggest = getHeaviest(shuf[1], shuf[2], shuf[3]);
		int middle = excl({shuf[1], shuf[2], shuf[3]}, {smallest, biggest});

		order1 = {smallest, middle, biggest};
	}

	{
		int smallest = getLightest(shuf[4], shuf[5], shuf[6]);
		int biggest = getHeaviest(shuf[4], shuf[5], shuf[6]);
		int middle = excl({shuf[4], shuf[5], shuf[6]}, {smallest, biggest});

		order2 = {smallest, middle, biggest};
	}

	vector<int> output;

	while (output.size() < 6)
	{
		if (order1.size() < order2.size()) {
			swap(order1, order2);
		}

		if (order2.size() == 0) {
			for (int x : order1)
				output.push_back(x);
			order1.clear();
			continue;
		}

		if (order1.size() == 1) {
			int median = getMedian(order1[0], order2[0], output.back());

			if (median == order1[0]) {
				output.push_back(order1[0]);
				order1.erase(order1.begin());
				output.push_back(order2[0]);
				order2.erase(order2.begin());
			} else if (median == order2[0]) {
				output.push_back(order2[0]);
				order2.erase(order2.begin());
				output.push_back(order1[0]);
				order1.erase(order1.begin());
			} else {
				assert(false);
			}
			continue;
		}

		int median = getMedian(order1[0], order1[1], order2[0]);

		if (median == order2[0]) {
			output.push_back(order1[0]);
			order1.erase(order1.begin());
			output.push_back(order2[0]);
			order2.erase(order2.begin());
		} else if (median == order1[1]) {
			output.push_back(order1[0]);
			order1.erase(order1.begin());
			output.push_back(order1[0]);
			order1.erase(order1.begin());
		} else if (median == order1[0]) {
			output.push_back(order2[0]);
			order2.erase(order2.begin());
		}
	}

	answer(&output[0]);
}

#ifdef _DEBUG

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXN 6
#define MAX_ANSWER_CALLS 1

static int realC[MAXN];
static int ind[MAXN];
static int numQueries;
static int numAnswerCalls;

static int arr[300];
static int arraySize;
static int ptr;

static void readAll()
{
	ptr = 0;
	arraySize = 0;
	int x;
	cin >> x;
	arr[arraySize++] = x;

	for (int i = 0; i < arr[0] * 6; i++)
	{
		cin >> x;
		arr[arraySize++] = x;
		assert(arraySize <= 300);
	}
}

static int readInt()
{
	assert(ptr < arraySize);
	int res = arr[ptr++];
	return res;
}

static void initNewTest()
{
	for (int i = 0; i < MAXN; i++)
	{
		realC[i] = readInt();
		realC[i]--;
		ind[realC[i]] = i;
	}

	numQueries = 0;
	numAnswerCalls = 0;
}

void answer(int C[])
{
	int i;

	numAnswerCalls++;
	if (numAnswerCalls > MAX_ANSWER_CALLS)
		return;

	for (i = 0; i < 6; i++)
		printf("%d ", C[i]);
	printf("%d\n", numQueries);
}

static void checkQuery(int A, int B, int C, int D)
{
	if (D == -1)
	{
		if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
			assert(0);
		if (A == B || B == C || A == C)
			assert(0);
	}
	else
	{
		if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
			assert(0);
		if (A == B || A == C || A == D || B == C || B == D || C == D)
			assert(0);
	}
}

int getMedian(int A, int B, int C)
{
	numQueries++;
	checkQuery(A, B, C, -1);

	A--;
	B--;
	C--;

	if (ind[B] < ind[A] && ind[A] < ind[C])
		return A + 1;

	if (ind[C] < ind[A] && ind[A] < ind[B])
		return A + 1;

	if (ind[A] < ind[B] && ind[B] < ind[C])
		return B + 1;

	if (ind[C] < ind[B] && ind[B] < ind[A])
		return B + 1;

	return C + 1;
}

int getHeaviest(int A, int B, int C)
{
	numQueries++;
	checkQuery(A, B, C, -1);

	A--;
	B--;
	C--;

	if (ind[A] > ind[B] && ind[A] > ind[C])
		return A + 1;

	if (ind[B] > ind[A] && ind[B] > ind[C])
		return B + 1;

	return C + 1;
}

int getLightest(int A, int B, int C)
{
	numQueries++;
	checkQuery(A, B, C, -1);

	A--;
	B--;
	C--;

	if (ind[A] < ind[B] && ind[A] < ind[C])
		return A + 1;

	if (ind[B] < ind[A] && ind[B] < ind[C])
		return B + 1;

	return C + 1;
}

int getNextLightest(int A, int B, int C, int D)
{
	int allLess = 1;

	numQueries++;
	checkQuery(A, B, C, D);

	A--;
	B--;
	C--;
	D--;

	if (ind[A] > ind[D] || ind[B] > ind[D] || ind[C] > ind[D])
		allLess = 0;

	if (allLess == 1)
	{
		if (ind[A] < ind[B] && ind[A] < ind[C])
			return A + 1;

		if (ind[B] < ind[A] && ind[B] < ind[C])
			return B + 1;

		return C + 1;
	}

	if (ind[A] > ind[D])
	{
		if ((ind[A] < ind[B] || ind[B] < ind[D]) &&
			(ind[A] < ind[C] || ind[C] < ind[D]))
			return A + 1;
	}

	if (ind[B] > ind[D])
	{
		if ((ind[B] < ind[A] || ind[A] < ind[D]) &&
			(ind[B] < ind[C] || ind[C] < ind[D]))
			return B + 1;
	}

	return C + 1;
}

int main()
{

	readAll();
	fclose(stdin);

	int T, i;

	T = readInt();

	init(T);

	for (i = 1; i <= T; i++)
	{
		initNewTest();
		orderCoins();
	}

	return 0;
}

#endif

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:20:15: warning: unused parameter 'T' [-Wunused-parameter]
   20 | void init(int T) {}
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:76:74: warning: conversion from 'std::chrono::duration<long int, std::ratio<1, 1000000000> >::rep' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   76 |  srand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

• Subtask 1: 56.770833 / 100