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<bits/stdc++.h>
#define MAXN 107
#include "koala.h"
using namespace std;
int b[MAXN],r[MAXN];
int minValue(int N, int W) {
b[0]=1;
playRound(b,r);
for(int i=0;i<N;i++){
if(r[i]==0)return i;
}
return 0;
}
vector<int> can,best;
void reset(){
best.clear(); can.clear();
for(int i=0;i<100;i++)b[i]=0;
}
int maxValue(int N, int W) {
reset();
for(int i=0;i<100;i++)can.push_back(i);
while(can.size()>1){
for(int i=0;i<100;i++)b[i]=0;
for(int i:can){
b[i]=W/int(can.size());
}
playRound(b,r);
for(int i:can){
if(r[i]>b[i])best.push_back(i);
}
can=best; best={};
}
return can[0];
}
int from[MAXN],to[MAXN];
bool compare(int x,int y){
for(int i=0;i<100;i++)b[i]=0;
int ll=0,rr=10,tt;
while(ll+1<rr){
tt=(ll+rr)/2;
b[x]=b[y]=tt;
playRound(b,r);
if(r[x]<=tt and r[y]<=tt){
rr=tt;
}else if(r[x]>tt and r[y]>tt){
ll=tt;
}else{
if(r[x]>=tt)return false;
else return true;
}
}
return false;
}
int greaterValue(int N, int W) {
if(compare(0,1))return 1;
else return 0;
}
vector<int> solve(vector<int> w,int p){
if(w.size()<=1)return w;
int pivot=p;
for(int i=0;i<100;i++)b[i]=0;
for(int i:w)b[i]=pivot;
playRound(b,r);
vector<int> ll,rr;
for(int i:w){
if(r[i]>pivot){
rr.push_back(i);
}else{
ll.push_back(i);
}
}
//if(ll.empty())return solve(w,p+1);
//if(rr.empty())return solve(w,p-1);
ll=solve(ll,100/int(ll.size()));
rr=solve(rr,100/int(rr.size()));
vector<int> res;
for(int i:ll)res.push_back(i);
for(int i:rr)res.push_back(i);
return res;
}
vector<int> s;
void allValues(int N, int W, int *P) {
s={};
for(int i=0;i<100;i++){
s.push_back(i);
}
solve(s,1);
for(int i=0;i<N;i++){
P[s[i]]=i+1;
}
}
# | 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... |