Submission #1057313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057313		MuhammadSaram	Scales (IOI15_scales)	C++17	100 / 100	24 ms	856 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"

using namespace std;

#define perm array<int, 6>
#define state vector<perm>
#define qu array<int, 4>

map<state,qu> nxt;

int maxx(perm &p,qu &q)
{
	return max(p[q[0]],max(p[q[1]],p[q[2]]));
}

int minn(perm &p,qu &q)
{
	return min(p[q[0]],min(p[q[1]],p[q[2]]));
}

int answer(perm &p,qu q)
{
	if (q[3]==-2)
	{
		int mx=maxx(p,q);
		for (int i=0;i<3;i++)
			if (mx==p[q[i]])
				return q[i];
	}
	else if(q[3]==-1)
	{
		int md=-maxx(p,q)-minn(p,q)+p[q[0]]+p[q[1]]+p[q[2]];
		for (int i=0;i<3;i++)
			if (md==p[q[i]])
				return q[i];
	}
	else if(!q[3])
	{
		int mn=minn(p,q);
		for (int i=0;i<3;i++)
			if (mn==p[q[i]])
				return q[i];
	}
	else
	{
		if (maxx(p,q)<p[q[3]])
		{
			int mn=minn(p,q);
			for (int i=0;i<3;i++)
				if (p[q[i]]==mn)
					return q[i];
		}
		int ans=7;
		for (int i=0;i<3;i++)
			if (p[q[i]]>p[q[3]])
				ans=min(ans,p[q[i]]);
		for (int i=0;i<3;i++)
			if (p[q[i]]==ans)
				return q[i];
	}
}

state whatif(state &v,qu &q,int ans)
{
	state res;
	for (perm p:v)
	{
		if (answer(p,q)==ans)
			res.push_back(p);
	}
	return res;
}

bool solve(state v,int cnt=729)
{
	if (v.size()<=1)
		return 1;
	qu q;
	for (q[0]=0;q[0]<6;q[0]++)
		for (q[1]=q[0]+1;q[1]<6;q[1]++)
			for (q[2]=q[1]+1;q[2]<6;q[2]++)
				for (q[3]=-2;q[3]<6;q[3]++)
				{
					if (q[3]==q[0] or q[3]==q[1] or q[3]==q[2])
						continue;
					state v1=whatif(v,q,q[0]);
					state v2=whatif(v,q,q[1]);
					state v3=whatif(v,q,q[2]);
					int mx=max(max(v2.size(),v3.size()),v1.size());
					if (mx<=cnt/3)
					{
						bool b=solve(v1,cnt/3) && solve(v2,cnt/3) && solve(v3,cnt/3);
						if (b)
						{
							nxt[v]=q;
							return 1;
						}
					}
				}
	return 0;
}

void init(int t)
{
	perm a = {0,1,2,3,4,5};
	state v;
	do
	{
		v.push_back(a);
	}while (next_permutation(a.begin(),a.end()));
	solve(v);
}

void orderCoins()
{
	perm a = {0,1,2,3,4,5};
	state v;
	do
	{
		v.push_back(a);
	}while (next_permutation(a.begin(),a.end()));
	for (int i=0;i<6;i++)
	{
		qu q=nxt[v];
		if (q[3]==-2)
			v=whatif(v,q,getHeaviest(q[0]+1,q[1]+1,q[2]+1)-1);
		else if(q[3]==-1)
			v=whatif(v,q,getMedian(q[0]+1,q[1]+1,q[2]+1)-1);
		else if(!q[3])
			v=whatif(v,q,getLightest(q[0]+1,q[1]+1,q[2]+1)-1);
		else
			v=whatif(v,q,getNextLightest(q[0]+1,q[1]+1,q[2]+1,q[3]+1)-1);
		if (v.size()==1)
			break;
	}
	int ans[6];
	for (int i=0;i<6;i++)
		for (int j=1;j<=6;j++)
			if (v[0][j-1]==i)
				ans[i]=j;
	answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'bool solve(std::vector<std::array<int, 6> >, int)':
scales.cpp:90:16: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
   90 |      int mx=max(max(v2.size(),v3.size()),v1.size());
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:104:15: warning: unused parameter 't' [-Wunused-parameter]
  104 | void init(int t)
      |           ~~~~^
scales.cpp: In function 'int answer(std::array<int, 6>&, std::array<int, 4>)':
scales.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

• Subtask 1: 100 / 100