Submission #357894

#	Time	Username	Problem	Language	Result	Execution time	Memory
357894		CaroLinda	Koala Game (APIO17_koala)	C++14	87 / 100	86 ms	492 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] ) ;
		}

	}

}

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

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

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

vector<int> solve(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 allValues(int N, int W, int *P) 
{

    if (W == 2*N) 
    {
    	vector<int> idx(N) ; iota(all(idx),0) ;
		vector<int> v = solve(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 ;
		for(int i = 0 ; i < N ; i++ ) b[i] = 1 ;

		playRound(b,r) ;
	
		for(int i = 0 ; i < N ; i++ ) 
			b[i] = (b[i] < r[i] ) ? 2 : 0 ;

		playRound(b,r) ;

		vector< vector<int> > quarters(4,vector<int>() ) ;

		for(int i = 0 ; i< N ; i++ )
		{
			if( b[i] == 2 )
			{
				if( b[i] < r[i] ) quarters[3].push_back(i) ;
				else quarters[2].push_back(i) ;
			}
			else
			{
				if( b[i] < r[i] ) quarters[1].push_back(i); 
				else quarters[0].push_back(i) ;
			}
		}

		for(int i = 0 ; i < 4 ; i++ ) random_shuffle(all(quarters[i] ) ) ;

		clean() ;

		for(int i = 0 ; i < sz(quarters[3] ) ; i++ )
		{
			b[ quarters[3][i] ] = 1 ;
			
			playRound(b,r) ;

			for(int j = 0 ; j < N ; j++ )
				if( P[j] == 0 && (b[j] >= r[j] ) ) P[j] = i+1 ;
		}

		vector<int> beg = {26,51,76} ;

		for(int i = 1 , x = 6 ; i < 4 ; i++, x++ )
		{
			
			vector<int> t = solve(quarters[i], x ) ;

			for(int j = beg[i-1] , k = 0 ; k < sz(t) ; k++ , j++ )
				P[ t[k] ] = j ;

		}

    }       	
}

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: 40 / 53