This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define pb push_back
#define sz(x) (int)x.size()
int n,w,b[105],r[105];
void reset(){
memset(b,0,sizeof b);
}
void play(){
playRound(b,r);
#ifdef DEBUG
for(int i=0;i<n;++i)pf("%2d ",b[i]);pf("\n");
for(int i=0;i<n;++i)pf("%2d ",r[i]);pf("\n");
#endif
}
int minValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
n=N;
reset();
b[0]=1;
play();
int ans=0;
if(r[0]==2){
for(int i=0;i<n;++i)if(r[i]==0)ans=i;
}
return ans;
}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
n=N;
reset();
for(int i=0;i<n;++i)b[i]=1;
play();
reset();
for(int i=0;i<n;++i)if(r[i]==2)b[i]=2;
play();
reset();
for(int i=0;i<n;++i)if(r[i]==3)b[i]=4;
play();
reset();
for(int i=0;i<n;++i)if(r[i]==5)b[i]=11;
play();
for(int i=0;i<n;++i)if(r[i]==12)return i;
return 0;
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
n=N;
int lo=1,hi=11,mid,res;
while(lo<=hi){
mid=(lo+hi)/2;
reset();
for(int i=0;i<2;++i)b[i]=mid;
play();
if(r[0]==0&&r[1]==0)hi=mid-1;
else if(r[0]>0&&r[1]>0)lo=mid+1;
else if(r[0]>r[1])return 0;
else return 1;
}
return 0;
}
void dnc(int lv,int rv,vector<int> &v,int *p){
if(lv==rv){
assert(sz(v)==1);
p[v[0]]=lv;
return;
}
reset();
for(int i:v)b[i]=w/sz(v);
play();
vector<int> tol,tor;
for(int i:v){
if(r[i]>b[i])tor.pb(i);
else tol.pb(i);
}
dnc(lv,lv+sz(tol)-1,tol,p);
dnc(lv+sz(tol),rv,tor,p);
}
int sqrt(int x){
for(int i=1;i<=10;++i){
if(i*i>=x)return i;
}
return 10;
}
void dnc2(int lv,int rv,vector<int> &v,int *p){
if(lv==rv){
assert(sz(v)==1);
p[v[0]]=lv;
return;
}
reset();
for(int i:v){
b[i]=min(sqrt(lv),w/sz(v));
}
play();
vector<int> tol,tor;
for(int i:v){
if(r[i]>b[i])tor.pb(i);
else tol.pb(i);
}
dnc2(lv,lv+sz(tol)-1,tol,p);
dnc2(lv+sz(tol),rv,tor,p);
}
void allValues(int N, int W, int *P) {
n=N;w=W;
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
vector<int> v;
for(int i=0;i<n;++i)v.pb(i);
dnc(1,n,v,P);
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
vector<int> v;
for(int i=0;i<n;++i)v.pb(i);
dnc2(1,n,v,P);
}
}
Compilation message (stderr)
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:70:24: warning: unused variable 'res' [-Wunused-variable]
70 | int lo=1,hi=11,mid,res;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |