Submission #358443

#	Time	Username	Problem	Language	Result	Execution time	Memory
358443		CaroLinda	Koala Game (APIO17_koala)	C++14	97 / 100	87 ms	520 KiB

koala

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

#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size() )

using namespace std ;

int b[100] , r[100] ;

void clean() { for(int i = 0 ; i < 100 ; i++ ) b[i] = 0 ; }

int minValue(int N, int W) 
{
	clean() ;

	b[0] = 1 ;
	playRound(b, r) ;

	if(r[0] < 2 ) return 0 ;

	for(int i = 1 ; i< 100 ; i++ )
		if( !r[i] ) return i ;
}

int maxValue(int N, int W) 
{

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

	while( sz(v) > 1 )
	{
		clean() ;
		
		for(auto e : v ) b[e] = 100/sz(v) ;
	
		playRound(b, r) ;

		aux.clear() ;
		for(auto e : v ) 
			if( r[e] > b[e] ) aux.push_back(e) ;

		swap(v,aux) ;
	}

	return v[0] ;

}

int greaterValue(int N, int W) 
{
	clean() ;
	b[0] = b[1] = 5 ;

	playRound(b,r) ;

	if( (b[0] < r[0] ) != (b[1] < r[1] ) ) return (b[1] < r[1] ) ;

	if( b[0] < r[0] )
	{
		b[0] = b[1] = 7 ;
		playRound(b,r) ;

		if( (b[0] < r[0] ) != (b[1] < r[1] ) ) return (b[1] < r[1] ) ;

		b[0] = b[1] = 8 ;
		playRound(b,r) ;

		return (b[1] < r[1] ) ;

	}
	else
	{
		b[0] = b[1] = 2 ;
		playRound(b,r) ;
		
		if( (b[0] < r[0] ) != (b[1] < r[1] ) ) return (b[1] < r[1] ) ;
		if(b[0] < r[0] )
		{
			b[0] = b[1] = 3 ;
			playRound(b,r) ;
			return (b[1] < r[1] ) ;
		}
		else
		{
			b[0] = b[1] = 1 ;
			playRound(b,r) ;
			return (b[1] < r[1] ) ;
		}

	}

}

int p[100] ;

bool isLarger(int x , int y, int t = 100  )
{
	clean() ;

	b[x] = b[y] = t ;
	playRound(b,r) ;

	return (b[x] < r[x] ) ;
}

vector<pair<int,int> > forbidden = {make_pair(92,96), make_pair(87,91), make_pair(84,86),
make_pair(76,79), make_pair(66,69), make_pair(61,64),
make_pair(58,60), make_pair(51,54), make_pair(47,49),
make_pair(39,41), make_pair(36,38), make_pair(31,33),
make_pair(26,28) } ;

vector<int> func(vector<int> idx , int x )
{
	vector<int> v = {idx[0], idx[1] } ;
	if( isLarger(idx[0], idx[1], x ) ) swap(v[0], v[1] );	

	for(int i = 2 ; i < sz(idx) ; i++ )
	{
		int l = 0 , r = sz(v)-1 , mid , best = -1 ;
		while( l <= r )
		{
			mid = (l+r)>>1 ;
			if( isLarger(idx[i], v[mid],x  ) )
			{
				best = mid ;
				l = mid+1 ;
			}
			else r = mid-1 ;
		}			

		vector<int> newV ;
		if( best == -1 ) newV.push_back(idx[i]) ;
			
		for(int j = 0 ; j < sz(v) ; j++ )
		{
			newV.push_back(v[j] ) ;
			if( j == best ) newV.push_back( idx[i] ) ;
		}

		swap(newV, v) ;

	}

	return v ;

}


void solve(vector<int> v, int R )
{

	if(sz(v) == 1 ) return (void)( p[ v[0] ] = R ) ;

	int w ;
	if( R <= 2 ) w = 1 ;
	else if(R <= 8 ) w = 2 ; 
	else if( R <= 30 ) w = 4 ;
	else if( R <= 84 ) w = 7 ;
	else w = 8 ;

	if( sz(v) == 2 )
	{
		clean() ;
		b[ v[0] ] = b[ v[1] ] = w ;
		p[ v[1] ] = R , p[ v[0] ] = R-1 ;

		playRound(b,r);

		if( b[ v[0] ] < r[ v[0] ] ) swap(p[v[1]], p[v[0]] ) ;

		return ;

	}

	int cost = R/sz(v) ;
	int L = R - sz(v) + 1 ;

	for(auto e : forbidden )
		if( make_pair(L,R) == e ) 
		{
			v=func(v,w) ;
			for(int i = sz(v)-1 ; i >= 0 ; i-- ) p[ v[i] ] = R-- ;
			return ;
		}

	clean() ;

	for(int i : v ) b[i] = cost ;

	playRound(b,r) ;

	vector<int> lef, rig ;

	for(int i : v ) 
	{
		if( b[i] < r[i] ) rig.push_back(i) ; 
		else lef.push_back(i) ;
	}

	if(sz(rig) ) solve(rig, R) ;
	if(sz(lef) ) solve(lef, R-sz(rig) ) ;

}

void allValues(int N, int W, int *P) 
{

    if (W == 2*N) 
    {
		vector<int> idx(N) ; iota(all(idx),0) ;
		vector<int> v = func(idx, 100 ) ;
 
		for(int i = 0 ; i < N ; i++ ) P[ v[i] ] = i+1 ;
    } 
    else 
    {
    	
		for(int i = 0 ; i < N ; i++ ) p[i] = 0 ;

		vector<int> v(N) ; iota(all(v), 0) ;
		solve(v,100) ;

		for(int i = 0 ; i < N ; i++ ) P[i] = p[i] ;

    }       	
}

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 50 / 53