Submission #1342949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342949		javkhlantogs	Koala Game (APIO17_koala)	C++20	73 / 100	35 ms	504 KiB

koala

#include<bits/stdc++.h>
#include "koala.h"
#define ll long long
using namespace std;
int i,j,k,q;
int b[100],r[100],a[100];
vector<vector<int>> memory(100,vector<int>(100,-1));
int minValue(int n,int w){
	for(i=0 ; i<n ; i++) b[i]=0;
	b[0]=1;
	playRound(b,r);
	for(i=0 ; i<n ; i++){
		if(r[i]<=b[i]) return i;
	}
}
int maxValue(int n,int w){
	for(i=0 ; i<n ; i++) b[i]=1;
	playRound(b,r);
	while(1){
		ll cnt=0;
		for(i=0 ; i<n ; i++) if(r[i]>b[i] and b[i]!=0) cnt++; 
		if(cnt==1) for(i=0 ; i<n ; i++) if(r[i]>b[i] and b[i]!=0) return i;
		for(i=0 ; i<n ; i++){
			if(r[i]>b[i] and b[i]!=0) b[i]=100/cnt;
				else b[i]=0;
		}
		playRound(b,r);
	}
}
int greaterValue(int n,int w){
	int ok=0,ng=10;
	for(i=0 ; i<n ; i++) b[i]=0;
	while(ng-ok>1){
		int mid=(ng+ok)/2;
		b[0]=b[1]=mid;
		playRound(b,r);
		if(r[1]<=b[1] and r[0]<=b[0]) ng=mid;
			else if(r[0]>b[0] and r[1]>b[1]) ok=mid;
				else{
					if(r[0]<r[1]) return 1;
						else return 0;
				}
	}
}
bool cmp1(int x,int y){
	if(memory[x][y]!=-1) return memory[x][y];
	b[x]=b[y]=100;
	playRound(b,r);
	b[x]=b[y]=0;
	if(r[y]>100) memory[x][y]=1;
		else memory[x][y]=0;
	memory[y][x]=1-memory[x][y];
	return memory[x][y];
}
bool cmp2(int x,int y){
	if(memory[x][y]!=-1) return memory[x][y];
	int ok=0,ng=10;
	while(ng-ok>1){
		int mid=(ng+ok)/2;
		b[x]=b[y]=mid;
		playRound(b,r);
		b[x]=b[y]=0;
		if(r[x]<=b[x] and r[y]<=b[y]) ng=mid;
			else if(r[x]>b[x] and r[y]>b[y]) ok=mid;
				else{
					if(r[x]<r[y]) memory[x][y]=1;
						else memory[x][y]=0;
					memory[y][x]=1-memory[x][y];
					return memory[x][y];
				}
	}
}
void allValues(int n,int w,int *p){
	for(i=0 ; i<n ; i++) b[i]=0;
	for(i=0 ; i<n ; i++) a[i]=i;
	if(w==200){
		stable_sort(a,a+n,cmp1);
		for(i=0 ; i<n ; i++) p[a[i]]=i+1;
	}
		else{
			stable_sort(a,a+n,cmp2);
			for(i=0 ; i<n ; i++) p[a[i]]=i+1;
		}
}

Compilation message (stderr)

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

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