Submission #794122

#	Time	Username	Problem	Language	Result	Execution time	Memory
794122		prvocislo	Scales (IOI15_scales)	C++17	72.02 / 100	6 ms	852 KiB

scales

#include "scales.h"
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

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);
void answer(int C[]);
const int k = 6;
struct question { int typ; vector<int> c; };
int ask(question q)
{
	if (q.typ == 0) return getLightest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
	if (q.typ == 1) return   getMedian(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
	if (q.typ == 2) return getHeaviest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1) - 1;
	return getNextLightest(q.c[0] + 1, q.c[1] + 1, q.c[2] + 1, q.c[3] + 1) - 1;
}
struct permutacia
{
	vector<int> p;
	int ans(const question &q)
	{
		if (q.typ == 3)
		{
			for (int i = 0; i < k; i++) if (p[i] == q.c.back())
				for (int j = i + 1; j < k; j++) if (count(q.c.begin(), q.c.end(), p[j])) return p[j];
			for (int j = 0; j < k; j++) if (count(q.c.begin(), q.c.end(), p[j])) return p[j];
		}
		vector<int> v;
		int cnt = 0;
		for (int j = 0; j < k; j++)
		{
			if (count(q.c.begin(), q.c.end(), p[j])) cnt++;
			if (cnt == q.typ + 1) return p[j];
		}
	}
};
struct node
{
	vector<permutacia> can;
	int id; vector<int> sons;
	node() { id = 0, sons.resize(6, -1); }
} tr[2000];
int cnt = 1;
vector<question> v; // 75 otazok
void fill(int vr)
{
	if (tr[vr].can.size() == 1) return;
	else if (tr[vr].can.size() == 720) tr[vr].id = 0; // opytame sa na najlahsi z prvych troch
	else if (tr[vr].can.size() == 120) tr[vr].id = 116; // opytame sa na najtazsi z poslednych troch
	else
	{
		int best = tr[vr].can.size();
		for (int q = 0; q < v.size(); q++)
		{
			vector<int> num(k, 0);
			for (permutacia& i : tr[vr].can) num[i.ans(v[q])]++;
			int maxi = *max_element(num.begin(), num.end());
			if (maxi < best) best = maxi, tr[vr].id = q;
			if (best == (tr[vr].can.size() + 2) / 3) break;
		}
	}
	vector<vector<permutacia> > syn(k);
	for (permutacia& i : tr[vr].can) syn[i.ans(v[tr[vr].id])].push_back(i);
	for (int i = 0; i < k; i++) if (syn[i].size())
	{
		tr[cnt].can = syn[i], tr[vr].sons[i] = cnt;
		fill(cnt++);
	}
}
void init(int T)
{
	permutacia p;
	for (int i = 0; i < k; i++) p.p.push_back(i);
	tr[0].can.push_back(p);
	while (next_permutation(p.p.begin(), p.p.end())) tr[0].can.push_back(p);
	for (int a = 0; a < k; a++) for (int b = a + 1; b < k; b++) for (int c = b + 1; c < k; c++)
	{
		for (int typ = 0; typ < 3; typ++) v.push_back({ typ, {a, b, c} });
		for (int d = 0; d < k; d++) if (a != d && b != d && c != d) v.push_back({ 3, {a, b, c, d} });
	}
	fill(0);
}
int ans[k];
void orderCoins()
{
	int vr = 0;
	while (tr[vr].can.size() > 1)
	{
		vr = tr[vr].sons[ask(v[tr[vr].id])];
	}
	for (int i = 0; i < k; i++) ans[i] = tr[vr].can[0].p[i] + 1;
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void fill(int)':
scales.cpp:58:29: warning: conversion from 'std::vector<permutacia>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |   int best = tr[vr].can.size();
      |              ~~~~~~~~~~~~~~~^~
scales.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<question>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int q = 0; q < v.size(); q++)
      |                   ~~^~~~~~~~~~
scales.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<permutacia>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    if (best == (tr[vr].can.size() + 2) / 3) break;
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:76:15: warning: unused parameter 'T' [-Wunused-parameter]
   76 | void init(int T)
      |           ~~~~^
scales.cpp: In member function 'int permutacia::ans(const question&)':
scales.cpp:34:15: warning: control reaches end of non-void function [-Wreturn-type]
   34 |   vector<int> v;
      |               ^

• Subtask 1: 72.02381 / 100