Submission #166435

#	Time	Username	Problem	Language	Result	Execution time	Memory
166435		dolphingarlic	Koala Game (APIO17_koala)	C++14	100 / 100	137 ms	508 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#define e begin()
#define f end()
#define w vector<int>
using namespace std;int B[100],R[100];bool u(int a,int b,int N,int W){fill(B,B+N,0);B[a]=B[b]=W;playRound(B,R);return(R[b]>W);}w g(w v,int N,int W){if(v.size()==1)return v;w a,b;a.insert(a.e,v.e,v.e+(v.size()+1)/2);b.insert(b.e,v.e+(v.size()+1)/2,v.f);a=g(a,N,W),b=g(b,N,W);w s;int t=0,y=0;while(t<a.size()&&y<b.size()){if(u(a[t],b[y],N,W))s.push_back(a[t++]);else s.push_back(b[y++]);}s.insert(s.f,a.e+t,a.f);s.insert(s.f,b.e+y,b.f);return s;}void q(w v,int N,int W,int* P,int l=1,int r=100){if(l ==r)P[v[0]]=l;else{int x=min((int)sqrt(2 * l),W/(r-l+1));fill(B,B+N,0);for(int i:v)B[i]=x;playRound(B,R);w L,G;for(int i:v)if(R[i]>x)G.push_back(i);else L.push_back(i);q(L,N,W,P,l,l+L.size()-1);q(G,N,W,P,r-G.size()+1,r);}}int minValue(int N,int W){fill(B,B+N,0);B[0]=1;playRound(B,R);if(R[0]<2)return 0;else for(int i=1;i<N;i++)if(!R[i])return i;}int maxValue(int N,int W){w v;for(int i=0;i<N;i++)v.push_back(i);while(v.size()!=1){int k=W/v.size();fill(B,B+N,0);for(int i:v)B[i]=k;playRound(B,R);v.clear();for(int i=0;i<N;i++)if(R[i]>k)v.push_back(i);}return v[0];}int greaterValue(int N,int W){int l=1,r=9;while(l !=r){int m=(l+r)/2;B[0]=B[1]=m;playRound(B,R);if(R[0]>m &&R[1]>m)l=m+1;else if(R[0] <=m &&R[1] <=m)r=m-1;else return(R[0]<R[1]);}B[0]=B[1]=l;playRound(B,R);return(R[0]<R[1]);}void allValues(int N,int W,int *P){if(W ==2 * N){w v;for(int i=0;i<N;i++)v.push_back(i);w s=g(v,N,W/2);for(int i=0;i<N;i++)P[s[i]]=i+1;} else{w v;for(int i=0;i<N;i++)v.push_back(i);q(v,N,W,P);}}

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> g(std::vector<int>, int, int)':
koala.cpp:6:298: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 using namespace std;int B[100],R[100];bool u(int a,int b,int N,int W){fill(B,B+N,0);B[a]=B[b]=W;playRound(B,R);return(R[b]>W);}w g(w v,int N,int W){if(v.size()==1)return v;w a,b;a.insert(a.e,v.e,v.e+(v.size()+1)/2);b.insert(b.e,v.e+(v.size()+1)/2,v.f);a=g(a,N,W),b=g(b,N,W);w s;int t=0,y=0;while(t<a.size()&&y<b.size()){if(u(a[t],b[y],N,W))s.push_back(a[t++]);else s.push_back(b[y++]);}s.insert(s.f,a.e+t,a.f);s.insert(s.f,b.e+y,b.f);return s;}void q(w v,int N,int W,int* P,int l=1,int r=100){if(l ==r)P[v[0]]=l;else{int x=min((int)sqrt(2 * l),W/(r-l+1));fill(B,B+N,0);for(int i:v)B[i]=x;playRound(B,R);w L,G;for(int i:v)if(R[i]>x)G.push_back(i);else L.push_back(i);q(L,N,W,P,l,l+L.size()-1);q(G,N,W,P,r-G.size()+1,r);}}int minValue(int N,int W){fill(B,B+N,0);B[0]=1;playRound(B,R);if(R[0]<2)return 0;else for(int i=1;i<N;i++)if(!R[i])return i;}int maxValue(int N,int W){w v;for(int i=0;i<N;i++)v.push_back(i);while(v.size()!=1){int k=W/v.size();fill(B,B+N,0);for(int i:v)B[i]=k;playRound(B,R);v.clear();for(int i=0;i<N;i++)if(R[i]>k)v.push_back(i);}return v[0];}int greaterValue(int N,int W){int l=1,r=9;while(l !=r){int m=(l+r)/2;B[0]=B[1]=m;playRound(B,R);if(R[0]>m &&R[1]>m)l=m+1;else if(R[0] <=m &&R[1] <=m)r=m-1;else return(R[0]<R[1]);}B[0]=B[1]=l;playRound(B,R);return(R[0]<R[1]);}void allValues(int N,int W,int *P){if(W ==2 * N){w v;for(int i=0;i<N;i++)v.push_back(i);w s=g(v,N,W/2);for(int i=0;i<N;i++)P[s[i]]=i+1;} else{w v;for(int i=0;i<N;i++)v.push_back(i);q(v,N,W,P);}}
                                                                                                                                                                                                                                                                                                         ~^~~~~~~~~
koala.cpp:6:310: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 using namespace std;int B[100],R[100];bool u(int a,int b,int N,int W){fill(B,B+N,0);B[a]=B[b]=W;playRound(B,R);return(R[b]>W);}w g(w v,int N,int W){if(v.size()==1)return v;w a,b;a.insert(a.e,v.e,v.e+(v.size()+1)/2);b.insert(b.e,v.e+(v.size()+1)/2,v.f);a=g(a,N,W),b=g(b,N,W);w s;int t=0,y=0;while(t<a.size()&&y<b.size()){if(u(a[t],b[y],N,W))s.push_back(a[t++]);else s.push_back(b[y++]);}s.insert(s.f,a.e+t,a.f);s.insert(s.f,b.e+y,b.f);return s;}void q(w v,int N,int W,int* P,int l=1,int r=100){if(l ==r)P[v[0]]=l;else{int x=min((int)sqrt(2 * l),W/(r-l+1));fill(B,B+N,0);for(int i:v)B[i]=x;playRound(B,R);w L,G;for(int i:v)if(R[i]>x)G.push_back(i);else L.push_back(i);q(L,N,W,P,l,l+L.size()-1);q(G,N,W,P,r-G.size()+1,r);}}int minValue(int N,int W){fill(B,B+N,0);B[0]=1;playRound(B,R);if(R[0]<2)return 0;else for(int i=1;i<N;i++)if(!R[i])return i;}int maxValue(int N,int W){w v;for(int i=0;i<N;i++)v.push_back(i);while(v.size()!=1){int k=W/v.size();fill(B,B+N,0);for(int i:v)B[i]=k;playRound(B,R);v.clear();for(int i=0;i<N;i++)if(R[i]>k)v.push_back(i);}return v[0];}int greaterValue(int N,int W){int l=1,r=9;while(l !=r){int m=(l+r)/2;B[0]=B[1]=m;playRound(B,R);if(R[0]>m &&R[1]>m)l=m+1;else if(R[0] <=m &&R[1] <=m)r=m-1;else return(R[0]<R[1]);}B[0]=B[1]=l;playRound(B,R);return(R[0]<R[1]);}void allValues(int N,int W,int *P){if(W ==2 * N){w v;for(int i=0;i<N;i++)v.push_back(i);w s=g(v,N,W/2);for(int i=0;i<N;i++)P[s[i]]=i+1;} else{w v;for(int i=0;i<N;i++)v.push_back(i);q(v,N,W,P);}}
                                                                                                                                                                                                                                                                                                                     ~^~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:6:845: warning: control reaches end of non-void function [-Wreturn-type]
 using namespace std;int B[100],R[100];bool u(int a,int b,int N,int W){fill(B,B+N,0);B[a]=B[b]=W;playRound(B,R);return(R[b]>W);}w g(w v,int N,int W){if(v.size()==1)return v;w a,b;a.insert(a.e,v.e,v.e+(v.size()+1)/2);b.insert(b.e,v.e+(v.size()+1)/2,v.f);a=g(a,N,W),b=g(b,N,W);w s;int t=0,y=0;while(t<a.size()&&y<b.size()){if(u(a[t],b[y],N,W))s.push_back(a[t++]);else s.push_back(b[y++]);}s.insert(s.f,a.e+t,a.f);s.insert(s.f,b.e+y,b.f);return s;}void q(w v,int N,int W,int* P,int l=1,int r=100){if(l ==r)P[v[0]]=l;else{int x=min((int)sqrt(2 * l),W/(r-l+1));fill(B,B+N,0);for(int i:v)B[i]=x;playRound(B,R);w L,G;for(int i:v)if(R[i]>x)G.push_back(i);else L.push_back(i);q(L,N,W,P,l,l+L.size()-1);q(G,N,W,P,r-G.size()+1,r);}}int minValue(int N,int W){fill(B,B+N,0);B[0]=1;playRound(B,R);if(R[0]<2)return 0;else for(int i=1;i<N;i++)if(!R[i])return i;}int maxValue(int N,int W){w v;for(int i=0;i<N;i++)v.push_back(i);while(v.size()!=1){int k=W/v.size();fill(B,B+N,0);for(int i:v)B[i]=k;playRound(B,R);v.clear();for(int i=0;i<N;i++)if(R[i]>k)v.push_back(i);}return v[0];}int greaterValue(int N,int W){int l=1,r=9;while(l !=r){int m=(l+r)/2;B[0]=B[1]=m;playRound(B,R);if(R[0]>m &&R[1]>m)l=m+1;else if(R[0] <=m &&R[1] <=m)r=m-1;else return(R[0]<R[1]);}B[0]=B[1]=l;playRound(B,R);return(R[0]<R[1]);}void allValues(int N,int W,int *P){if(W ==2 * N){w v;for(int i=0;i<N;i++)v.push_back(i);w s=g(v,N,W/2);for(int i=0;i<N;i++)P[s[i]]=i+1;} else{w v;for(int i=0;i<N;i++)v.push_back(i);q(v,N,W,P);}}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ^

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