Submission #111473

#	Time	Username	Problem	Language	Result	Execution time	Memory
111473		nxteru	Koala Game (APIO17_koala)	C++14	100 / 100	88 ms	512 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,vector<int>> P;
typedef pair<ll,P> T;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000001
int n,b[105],r[105];
void ini(void){
	for(int i=0;i<n;i++)b[i]=0;
}
int minValue(int N, int w) {
	n=N;
    ini();
    b[0]=1;
    playRound(b,r);
    for(int i=0;i<n;i++)if(b[i]>=r[i])return i;
}

int maxValue(int N,int w) {
	n=N;
    vector<int>res;
    for(int i=0;i<n;i++)res.PB(i);
    while(res.size()>1){
		ini();
		for(int i=0;i<res.size();i++)b[res[i]]=w/res.size();
		playRound(b,r);
		res.clear();
		for(int i=0;i<n;i++)if(b[i]>0&&b[i]<r[i])res.PB(i);
	}
    return res[0];
}

int greaterValue(int N, int w) {
	n=N;
	ini();
	b[0]=4,b[1]=4;
	playRound(b,r);
	if(b[0]<r[0]){
		if(b[1]>=r[1])return 0;
		b[0]=7,b[1]=7;
		playRound(b,r);
		if(b[0]<r[0]&&b[1]<r[1]){
			b[0]=8,b[1]=8;
			playRound(b,r);
		}
		if(b[0]<r[0])return 0;
		else return 1;
	}else if(b[1]<r[1])return 1;
	else{
		b[0]=2,b[1]=2;
		playRound(b,r);
		if(b[0]>=r[0]&&b[1]>=r[1]){
			b[0]=1,b[1]=1;
			playRound(b,r);
		}
		if(b[0]<r[0])return 0;
		else return 1;
	}
}
bool grt(int x,int y){
	ini();
	b[x]=100,b[y]=100;
	playRound(b,r);
	return b[x]>=r[x];
}
vector<int> mrg(vector<int>x,vector<int>y){
	vector<int>res;
	int i=0,j=0;
	while(i<x.size()&&j<y.size()){
		if(grt(x[i],y[j]))res.PB(x[i++]);
		else res.PB(y[j++]);
	}
	while(i<x.size())res.PB(x[i++]);
	while(j<y.size())res.PB(y[j++]);
	return res;
}
void allValues(int N, int w, int *p) {
	n=N;
    if(w==2*n){
		vector<vector<int>>res;
		for(int i=0;i<n;i++)res.PB(vector<int>{i});
		while(res.size()>1){
			vector<vector<int>>nw;
			for(int i=0;i+1<res.size();i+=2){
				nw.PB(mrg(res[i],res[i+1]));
			}
			if(res.size()%2==1)nw.PB(res.back());
			res.clear();
			res.insert(res.begin(),nw.begin(),nw.end());
		}
		for(int i=0;i<n;i++)p[res[0][i]]=i+1;
    }else{
        stack<P>res;
        vector<int>o,e;
        for(int i=0;i<n;i++)b[i]=1;
        playRound(b,r);
        for(int i=0;i<n;i++){
			if(b[i]<r[i])e.PB(i);
			else o.PB(i);
		}
        res.push(P(1,o));
        res.push(P(o.size()+1,e));
        while(!res.empty()){
			int x=res.top().F;
			o=res.top().S;
			int s=o.size();
			res.pop();
			if(s==1){
				p[o[0]]=x;
				continue;
			}
			for(int i=1;i<=w;i++){
				if(i*s>w)continue;
				if(s<i+1){
					int q=0,c=i+1-s;
					for(int j=1;j<=n&&c>0;j++){
						if(j<x||x+s-1<j){
							q+=j;
							c--;
						}
					}
					if(x+s-1<=q)continue;
				}
				if((i+1)*s<=w){
					int q=0,c=w-(i+1)*s+i+1;
					for(int j=n;j>=1&&c>0;j--){
						if(j<x||x+s-1<j){
							if(c<=i+1)q+=j;
							c--;
						}	
					}
					if(x>q)continue;
				}
				ini();
				for(int j=0;j<s;j++)b[o[j]]=i;
				playRound(b,r);
				vector<int>v,u;
				for(int j=0;j<s;j++){
					if(b[o[j]]<r[o[j]])u.PB(o[j]);
					else v.PB(o[j]);
				}
				res.push(P(x,v));
				res.push(P(x+v.size(),u));
				break;
			}
		}
    }
}

Compilation message (stderr)

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<res.size();i++)b[res[i]]=w/res.size();
               ~^~~~~~~~~~~
koala.cpp: In function 'std::vector<int> mrg(std::vector<int>, std::vector<int>)':
koala.cpp:75:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<x.size()&&j<y.size()){
        ~^~~~~~~~~
koala.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<x.size()&&j<y.size()){
                    ~^~~~~~~~~
koala.cpp:79:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<x.size())res.PB(x[i++]);
        ~^~~~~~~~~
koala.cpp:80:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j<y.size())res.PB(y[j++]);
        ~^~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i+1<res.size();i+=2){
                ~~~^~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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