Submission #130494

#	Time	Username	Problem	Language	Result	Execution time	Memory
130494		sebinkim	Koala Game (APIO17_koala)	C++14	100 / 100	85 ms	888 KiB

koala

#include <bits/stdc++.h>

#include "koala.h"

using namespace std;

int minValue(int n, int w)
{
	int B[111], R[111];
	int i;
	
	for(i=0; i<n; i++){
		B[i] = 1;
	}
	
	playRound(B, R);
	
	for(i=0; i<n; i++){
		if(R[i] == 2) break;
		B[i] = 0;
	}
	
	B[i] = 1;
	
	for(i++; i<n; i++){
		B[i] = 0;
	}
	
	playRound(B, R);
	
	for(i=0; i<n; i++){
		if(!R[i]) return i;
	}
	
    return 0;
}

int maxValue(int n, int w)
{
	int B[111], R[111];
	int i, s, k;
	
	for(i=0; i<n; i++){
		B[i] = 1;
	}
	
	for(k=1, s=n; s>1; ){
		for(i=0; i<n; i++){
			B[i] *= k;
		}
		
		playRound(B, R);
		
		for(i=0, s=0; i<n; i++){
			if(B[i] == k && R[i] > k){
				B[i] = 1; s ++;
			}
			else B[i] = 0;
		}
		
		k = n / s;
	}
	
	for(i=0; i<n; i++){
		if(B[i]) return i;
	}
	
	return 0;
}

int greaterValue(int n, int w)
{
	int B[111], R[111];
	int N[6] = {1, 2, 3, 4, 6, 10};
	int i, s, e, m;
	
	for(s=0, e=5; s<=e; ){
		m = s + e >> 1;
		
		for(i=0; i<n; i++){
			B[i] = 0;
		}
		
		B[0] = B[1] = N[m];
		
		playRound(B, R);
		
		if(R[0] && R[1]) s = m + 1;
		else if(!R[0] && !R[1]) e = m - 1;
		else return !R[0];
	}
	
	return 0;
}

void dnc(int n, vector <int> &V, int l, int r, int *K, int *P, int &x)
{
	if(l == r) P[V[0]] = l;
	else{
		vector <int> X, Y;
		int B[111], R[111];
		int i;
		
		for(i=0; i<n; i++){
			B[i] = 0;
		}
		
		for(int &t: V){
			B[t] = K[x];
		}
		
		playRound(B, R);
		
		for(int &t: V){
			if(R[t] > K[x]) Y.push_back(t);
			else X.push_back(t);
		}
		
		x ++;
		
		dnc(n, X, l, l + X.size() - 1, K, P, x);
		dnc(n, Y, l + X.size(), r, K, P, x);
	}
}

void allValues(int n, int w, int *P)
{
	if(n + n == w){
		int D[111], B[111], R[111];
		int i, j, s, e, m;
		
		for(i=0; i<n; i++){
			for(s=0, e=i-1; s<=e; ){
				m = s + e >> 1;
				
				for(j=0; j<n; j++){
					B[j] = 0;
				}
				
				B[i] = B[D[m]] = n;
				
				playRound(B, R);
				
				if(!R[i]) e = m - 1;
				else s = m + 1;
			}
			
			for(j=i; j>e+1; j--){
				D[j] = D[j - 1];
			}
			
			D[e + 1] = i;
		}
		
		for(i=0; i<n; i++){
			P[D[i]] = i + 1;
		}
	}
	else{
		vector <int> V;
		int K[111] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 4, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 5, 1, 2, 2, 3, 5, 3, 4, 5, 2, 5, 2, 3, 4, 5, 4, 4, 6, 1, 2, 3, 5, 6, 3, 4, 6, 5, 6, 1, 4, 5, 6, 1, 7, 1, 2, 2, 2, 3, 4, 5, 7, 3, 4, 7, 5, 6, 7, 2, 5, 6, 7, 2, 2, 3, 4, 5, 6, 8, 3, 4, 6, 8, 5, 8, 6, 8};
		int i, x;
		
		for(i=0; i<n; i++){
			V.push_back(i);
		}
		
		x = 0;
		
		dnc(n, V, 1, n, K, P, x);
	}
}

Compilation message (stderr)

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:78:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   m = s + e >> 1;
       ~~^~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:134:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     m = s + e >> 1;
         ~~^~~

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