#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int minValue(int N, int W) {
int a[N], b[N];
a[0] = 1;
for(int i = 1; i < N; i++) a[i] = 0;
playRound(a, b);
for(int i = 0; i < N; i++) if(!b[i]) return i;
return 0;
}
int maxValue(int N, int W) {
int a[N], b[N];
for(int i = 0; i < N; i++) a[i] = 1;
playRound(a, b);
set<int> s;
for(int i = 0; i < N; i++) if(b[i]) s.insert(i);
memset(a, 0, sizeof(a));
for(int i : s) a[i] = 2;
playRound(a, b);
for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
memset(a, 0, sizeof(a));
for(int i : s) a[i] = 4;
playRound(a, b);
for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
memset(a, 0, sizeof(a));
for(int i : s) a[i] = 11;
playRound(a, b);
for(int i = 0; i < N; i++) if(s.find(i) != s.end() && !b[i]) s.erase(i);
return *s.begin();
}
int greaterValue(int N, int W) {
int a[N], b[N];
memset(a, 0, sizeof(a));
int l = 1, r = 9, m;
while(l <= r) {
m = (l+r)/2;
a[0] = a[1] = m;
playRound(a, b);
if(b[0] && b[1]) l = m+1;
else if(!b[0] && !b[1]) r = m-1;
else if(b[0] && !b[1]) return 0;
else return 1;
}
return 0;
}
int a[100], b[100], c[100], tmp[100];
bool cmp(int x, int y) {
if(x == y) return false;
a[x] = a[y] = 100;
playRound(a, b);
a[x] = a[y] = 0;
return b[y] > 100;
}
void srt(int l, int r) {
if(l == r) return;
int m = (l+r)/2;
srt(l, m);
srt(m+1, r);
int i = l, j = m+1, idx = l;
while(i <= m || j <= r) {
if(i > m) tmp[idx++] = c[j++];
else if(j > r) tmp[idx++] = c[i++];
else if(cmp(c[i], c[j])) tmp[idx++] = c[i++];
else tmp[idx++] = c[j++];
}
for(int i = l; i <= r; i++) c[i] = tmp[i];
}
int ans[100];
void solve(int l, int r, int c, vector<int> pos) {
//cout << l << " " << r << endl;
if(l > r) return;
if(pos.empty()) return;
if(l == r) {
//cout << l << " " << pos[0] << endl;
ans[pos[0]] = l;
return;
}
if(c == 0) c = min(100/(r-l+1), 8);
memset(a, 0, sizeof(a));
for(int i : pos) a[i] = c;
playRound(a, b);
//
int B[100], R[100], P[100];
for(int i = 0; i < 100; i++) P[i] = i+1;
memset(B, 0, sizeof(B));
for(int i = l-1; i < r; i++) B[i] = c;
int cache[2][205];
int num[2][205];
char taken[105][205];
for (int i=0;i<205;++i) {
cache[1][i] = 0;
num[1][i] = 0;
}
for (int i=0;i<N;++i) {
//cout << "b " << i << endl;
int v = B[i]+1;
int ii = i&1;
int o = ii^1;
for (int j=0;j<=W;++j) {
cache[ii][j] = cache[o][j];
num[ii][j] = num[o][j];
taken[i][j] = 0;
}
for (int j=W;j>=v;--j) {
int h = cache[o][j-v] + P[i];
int hn = num[o][j-v] + 1;
if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
cache[ii][j] = h;
num[ii][j] = hn;
taken[i][j] = 1;
} else {
taken[i][j] = 0;
}
}
}
int cur = W;
for (int i=N-1;i>=0;--i) {
R[i] = taken[i][cur] ? (B[i] + 1) : 0;
cur -= R[i];
}
//
int m = r+1;
for(int i = r-1; i >= l-1; i--) if(R[i] > B[i]) m = i+1;
vector<int> v1, v2;
for(int i : pos) {
if(b[i] > a[i]) v2.push_back(i);
else v1.push_back(i);
}
//cout << "a " << l << " " << m << " " << r << " " << c << endl;
//for(int i : v1) cout << i << " ";
//cout << endl;
//for(int i : v2) cout << i << " ";
//cout << endl;
if(v2.size() == 0) {
solve(l, m-1, c-1, v1);
} else if(v1.size() == 0) {
solve(m, r, c+1, v2);
} else {
solve(l, m-1, 0, v1);
solve(m, r, 0, v2);
}
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
for(int i = 0; i < N; i++) c[i] = i;
srt(0, N-1);
for(int i = 0; i < N; i++) P[c[i]] = i+1;
} else {
vector<int> v;
for(int i = 0; i < 100; i++) v.push_back(i);
solve(1, 100, 0, v);
for(int i = 0; i < 100; i++) P[i] = ans[i];
}
}
Compilation message
koala.cpp: In function 'void solve(int, int, int, std::vector<int>)':
koala.cpp:103:20: error: 'N' was not declared in this scope
103 | for (int i=0;i<N;++i) {
| ^
koala.cpp:108:25: error: 'W' was not declared in this scope
108 | for (int j=0;j<=W;++j) {
| ^
koala.cpp:113:20: error: 'W' was not declared in this scope
113 | for (int j=W;j>=v;--j) {
| ^
koala.cpp:125:15: error: 'W' was not declared in this scope
125 | int cur = W;
| ^
koala.cpp:126:16: error: 'N' was not declared in this scope
126 | for (int i=N-1;i>=0;--i) {
| ^
