Submission #230355

#	Time	Username	Problem	Language	Result	Execution time	Memory
230355		CaroLinda	Scales (IOI15_scales)	C++14	100 / 100	88 ms	504 KiB

scales

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

#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define ll long long 
#define debug printf
#define max3(a,b,c) max( a , max(b,c) )

using namespace std ;


int pot[10] ;
int cool[ 1500 ];
bool ended[1500] ;
vector< vector<int> > permutacoes ;
vector< pair<int, vector<int> > > operacoes ;

int get_pos(int pos )
{

	if( ended[pos] ) return cool[pos] ;

	pair<int, vector<int> > op = operacoes[ cool[pos] ] ;

	int resp ;

	if( op.ff == 1 ) resp = getLightest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
	else if( op.ff == 2 ) resp = getMedian( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
	else if( op.ff == 3 ) resp = getHeaviest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
	else resp = getNextLightest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1, op.ss[3] + 1 ) ;

	lp(i,0,3)
		if( resp == op.ss[i]+1 ) return get_pos( pos*3 + i ) ;

}

bool solve(int pos , int steps_left , vector<int> possible )
{
	if( possible.size() <= 1 )
	{
		if( possible.size() == 1 )
			cool[pos] = possible[0] , ended[pos] = true ;
		return true ;
	}

	for(int g = 0 ; g < (int)operacoes.size() ; g++ )
	{
		auto op = operacoes[g] ;

		bool ok = true ;

		vector<int> ans[3];

		for(auto p : possible )
		{
			int x = permutacoes[p][ op.ss[0] ] ;
			int y = permutacoes[p][ op.ss[1] ] ;
			int z = permutacoes[p][ op.ss[2] ] ;

			int val[3] = {x,y,z} , decode[6] ;
			
			sort(val,val+3) ;
			
			decode[x] = 0 ;
			decode[y] = 1 ;
			decode[z] = 2 ; 

			if(op.ff == 1) ans[ decode[ val[0] ] ].pb(p) ;
			else if(op.ff == 2) ans[ decode[ val[1] ] ].pb(p) ;
			else if(op.ff == 3) ans[ decode[ val[2] ] ].pb(p) ;
			else 
			{

				int w = permutacoes[p][ op.ss[3] ] ;

				if( w < val[0] || w > val[2] ) ans[ decode[ val[0] ] ].pb(p) ;
				else if ( w < val[1] ) ans[ decode[ val[1] ] ].pb(p) ;
				else ans[ decode[ val[2] ] ].pb(p) ;

			}

		}	

		if( (int)max( ans[0].size() , max( ans[1].size() , ans[2].size() ) ) > pot[steps_left-1] )
			continue ;


		lp(j,0,3)
			ok &= solve(pos*3 + j , steps_left - 1 , ans[j] ) ;

		if(ok) 
		{
			cool[pos] = g ;
			return true ;
		}

	}

	return false ;

}

bool isOn(int i, int m) { return ((1<<i)&m)!= 0 ; }

void init(int T)
{
	pot[0] = 1 ;
	for(int i = 1 ; i < 7 ; i++ ) pot[i] = 3*pot[i-1] ;

	vector<int> v(6) ;
	iota(all(v) , 0 ) ;

	do{
		permutacoes.pb(v) ;
	} while( next_permutation(all(v)) ) ;

	vector<int> lista( permutacoes.size() ) ;
	iota(all(lista), 0 ) ;

	for(int i = 0 ; i < (1<<6) ; i++ )
	{
		if( __builtin_popcount(i) != 3 ) continue ;

		vector<int> ligado ;
		for(int j = 0 ; j < 6 ; j++ )
			if( isOn(j,i) ) ligado.pb(j) ;

		lp(j,1,4) operacoes.pb( mk( j , ligado ) ) ;
		lp(j,0,6)
			if(!isOn(j,i)) 
			{
				ligado.pb(j) ;
				operacoes.pb( mk( 4 , ligado ) ); 
				ligado.pop_back() ;
			}

	}

	solve( 1 , 6 , lista ) ;

}
void orderCoins() {

	int pos = get_pos( 1 ) ;

	int W[6] ;

	lp(i,0,6) W[ permutacoes[pos][i] ] = i+1 ;

	answer(W) ;

}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:111:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^
scales.cpp: In function 'int get_pos(int)':
scales.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 100 / 100