| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1293130 | yf_yusuf | 코알라 (APIO17_koala) | C++20 | 0 ms | 0 KiB |
#include "koala.h"
int B[100], R[100];
int minValue(int N, int W) {
B[0] = 1;
playRound(B, R);
int j;
for(int i=0;i<N;i++){
if(!R[i])
j = i;
}
return j;
}
int maxValue(int N, int W) {
vll v;
for(int i=0;i<N;i++)v.pb(i);
while(v.size() > 1){
ll x = (W / v.size());
fill(B, B+N, 0);
for(auto i : v)B[i] = x;
playRound(B, R);
v.clear();
for(int i=0;i<N;i++)
if(R[i] > x)v.pb(i);
}
return v[0];
}
int i=0, j=1;
int greaterValue(int N, int W) {
ll l = 1, r = 9;
fill(B, B+N, 0);
while(l!=r){
ll m=(l+r)>>1;
B[i] = B[j] = m;
playRound(B, R);
if (R[i] > m && R[j] > m) l = m + 1;
else if (R[i] <= m && R[j] <= m) r = m - 1;
else return (R[i] < R[j]);
}
B[i] = B[j] = l;
playRound(B, R);
fill(B, B+N, 0);
return (R[i] < R[j]);
}
bool better(int i, int j, int N, int W){
fill(B, B+N, 0);
B[i] = B[j] = W / 2;
playRound(B, R);
return (R[j] > W/2);
}
bool BETTER(int I, int J, int N, int W){
i=I; j=J;
return greaterValue(N, W);
}
vll dac(vll v, int N, int W, bool ww = 0){
if(v.size() == 1)return v;
vll a, b;
int md = (v.size() + 1)/2;
for(int i=0 ;i<md ;i++)a.pb(v[i]);
for(int i=md;i<v.size();i++)b.pb(v[i]);
a = dac(a, N, W, ww);
b = dac(b, N, W, ww);
vll c;
int l=0,r=0;
while(l < a.size() && r < b.size()){
if((ww ? BETTER(a[l], b[r], N, W) : better(a[l], b[r], N, W)))
c.pb(a[l++]);
else
c.pb(b[r++]);
}
while(l < a.size())c.pb(a[l++]);
while(r < b.size())c.pb(b[r++]);
return c;
}
void split(vll v,ll N,ll W, int *P, ll l,ll r){
// for(auto i : v)cout<<i<<" ";cout<<l<<" "<<r<<" NW\n";
if(v.size() == 1)P[v[0]] = l;
else{
ll w = min((ll)(sqrt(2 * l)), W / (r-l+1));
fill(B, B+N, 0);
for(auto i : v)B[i] = w;
playRound(B, R);
vll ls, gr;
for(auto i : v){
(R[i] > w ? gr : ls).pb(i);
// cout<<R[i]<<" ";
}
// cout<<"r\n";
split(ls, N, W, P, l, l + ls.size() - 1);
split(gr, N, W, P, r - gr.size() + 1, r);
}
}
void allValues(int N, int W, int *P) {
if(N+N == W){
vll v;
for(int i=0;i<N;i++)v.pb(i);
v = dac(v, N, W);
for(int i=0;i<N;i++)P[v[i]] = i+1;
} else{
vll v;
for(int i=0;i<N;i++)v.pb(i);
split(v, N, W, P, 1, N);
}
}