Submission #1075857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075857		Elias	Scales (IOI15_scales)	C++17	46.02 / 100	1 ms	348 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};
	random_shuffle(shuf.begin(), shuf.end());
	shuf.insert(shuf.begin(), 0);

	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});

	order = {smallest, middle, biggest};

	insert(0, 2, shuf[4]);
	insert(0, 3, shuf[5]);
	insert(0, 4, shuf[6]);

	answer(&order[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) {}
      |           ~~~~^

• Subtask 1: 46.022727 / 100