#include "koala.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
int minValue(int N, int W) {
int B[N], R[N];
B[0] = 1;
playRound(B, R);
for(int i=0;i<N;i++){
if(R[i] > B[i]) continue;
else return i;
} assert(false);
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return 0;
}
int maxValue(int N, int W) {
vector<int> p(N);
for(int i=0;i<N;i++) p[i] = i;
while((int)p.size() > 1){
int v = W / (int)p.size();
int B[N], R[N];
for(auto x : p) B[x] = v;
playRound(B, R);
vector<int> t;
for(auto x : p){
if(B[x] < R[x]){
t.push_back(x);
}
}
swap(p, t);
}
assert((int)p.size() == 1);
return p[0];
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return 0;
}
int greaterValue(int N, int W) {
int is = -1;
auto ask = [&](int v){
int B[N], R[N];
B[0] = B[1] = v;
playRound(B, R);
int c = (R[0] > B[0]) + (R[1] > B[1]);
if(c == 1){
if(R[0] > B[0]) is = 0;
else is = 1;
} return c;
};
int l = 1, r = 8;
while(l < r){
int m = (l + r) >> 1;
int v = ask(m);
if(v == 1) break;
if(v == 2) l = m + 1;
else r = m - 1;
}
if(~is) return is;
assert(l == r);
ask(l);
return is;
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return 0;
}
#define ar array
void allValues(int N, int W, int *P) {
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
assert(false);
} else {
vector<int> pref(N + 1);
for(int i=1;i<=N;i++){
pref[i] = pref[i-1] + i;
}
auto check = [&](int l, int r, int v){
ar<int, 2> mx {-1, -1};
int lef = r;
for(int x=0;x<=(r - l + 1);x++){
if(x * (v + 1) > lef) continue;
int res = pref[N] - pref[r];
res += (pref[r] - pref[r - x]);
int rem = lef - x * (v + 1);
res += (pref[l - 1] - pref[max(0, l - 1 - rem)]);
mx = max(mx, {res, x});
}
assert(~mx[1]);
return mx[1];
};
auto ask = [&](vector<int> p, int v) -> ar<vector<int>, 2>{
int B[N], R[N];
for(auto x : p) B[x] = v;
playRound(B, R);
ar<vector<int>, 2> t;
for(auto x : p){
if(B[x] < R[x]) t[1].push_back(x);
else t[0].push_back(x);
} return t;
};
int cnt = 0;
function<void(int, int, vector<int>)> go = [&](int l, int r, vector<int> p){
assert(r - l + 1 == (int)p.size());
if(l == r){
assert((int)p.size() == 1);
P[p[0]] = l;
return;
}
//~ cout<<l<<" "<<r<<endl;
int h = (r - l + 1) >> 1;
int lx = 1, rx = min(8, r / (r - l + 1));
while(lx < rx){
int m = (lx + rx) >> 1;
int y = check(l, r, m);
if(y <= h) rx = m;
else lx = m + 1;
}
if(lx > 1){
int y1 = check(l, r, lx);
int y2 = check(l, r, lx - 1);
if(abs(y1 - h) <= abs(y2 - h)){
ar<vector<int>, 2> t = ask(p, lx);
int m = r - y1; cnt++;
go(l, m, t[0]);
go(m + 1, r, t[1]);
} else {
ar<vector<int>, 2> t = ask(p, lx + 1);
int m = r - y2; cnt++;
go(l, m, t[0]);
go(m + 1, r, t[1]);
}
} else {
ar<vector<int>, 2> t = ask(p, lx);
int y = check(l, r, lx);
int m = r - y; cnt++;
go(l, m, t[0]);
go(m + 1, r, t[1]);
}
};
vector<int> p(N);
iota(p.begin(), p.end(), 0);
go(1, N, p);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
