#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "koala.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
////
//static int N, W;
//static int P[105];
//
//static int maxQueries = 3200;
//static int numQueries;
//
//static void runGame(int F);
//static void grader();
//
//void playRound(int *B, int *R) {
// int i, j;
//
// int S = 0;
// for (i=0;i<N;++i) {
// if ( !(B[i] >= 0 && B[i] <= W) ) {
// printf("Invalid query.\n");
// exit(0);
// }
// S += B[i];
// }
// if (S > W) {
// printf("Invalid query.\n");
// exit(0);
// }
//
// numQueries++;
// if (numQueries > maxQueries) {
// printf("Too many queries.\n");
// exit(0);
// }
//
// int cache[2][205];
// int num[2][205];
// char taken[105][205];
//
// for (i=0;i<205;++i) {
// cache[1][i] = 0;
// num[1][i] = 0;
// }
//
// for (i=0;i<N;++i) {
// int v = B[i]+1;
// int ii = i&1;
// int o = ii^1;
// for (j=0;j<=W;++j) {
// cache[ii][j] = cache[o][j];
// num[ii][j] = num[o][j];
// taken[i][j] = 0;
// }
// for (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 (i=N-1;i>=0;--i) {
// R[i] = taken[i][cur] ? (B[i] + 1) : 0;
// cur -= R[i];
// }
//}
int minValue(int N, int W) {
int B[105];
int R[105];
memset(B, 0, sizeof(B));
memset(R, 0, sizeof(R));
B[0] = 1;
playRound(B, R);
for (int i = 0; i < N; ++i)
if (R[i] == 0) return i;
return 0;
}
int maxValue(int N, int W) {
vector <int> cands;
for (int i = 0; i < N; ++i) cands.push_back(i);
while (cands.size() > 1) {
int B[105];
int R[105];
memset(B, 0, sizeof(B));
memset(R, 0, sizeof(R));
for (auto x: cands) B[x] = W / cands.size();
playRound(B, R);
vector <int> ncands;
int maxi = *max_element(R, R + N);
for (auto x: cands)
if (R[x] == maxi) ncands.push_back(x);
swap(cands, ncands);
}
return cands[0];
}
int greaterValue(int N, int W) {
int lo = 0, hi = W / 6;
while (lo <= hi) {
int mid = lo + hi >> 1;
int B[105];
int R[105];
memset(B, 0, sizeof(B));
memset(R, 0, sizeof(R));
B[0] = B[1] = mid;
playRound(B, R);
int ok0 = (R[0] > mid);
int ok1 = (R[1] > mid);
if (ok0 ^ ok1) return (ok0 ? 0 : 1);
if (!ok0) hi = mid - 1;
else lo = mid + 1;
}
}
void allValues(int N, int W, int *P) {
if (W != 2 * N) {
int p[N];
memset(p, 0, sizeof(p));
for (int i = 0; i < N; ++i) p[i] = i;
sort(p, p + N, [&](int u, int v) {
int lo = 0, hi = W / 6;
while (lo <= hi) {
int mid = lo + hi >> 1;
int B[105];
int R[105];
memset(B, 0, sizeof(B));
memset(R, 0, sizeof(R));
B[u] = B[v] = mid;
playRound(B, R);
int ok0 = (R[u] > mid);
int ok1 = (R[v] > mid);
if (ok0 ^ ok1) return (ok0 ? 0 : 1);
if (!ok0) hi = mid - 1;
else lo = mid + 1;
}
});
for (int i = 0; i < N; ++i) P[p[i]] = i + 1;
} else {
int p[N];
memset(p, 0, sizeof(p));
for (int i = 0; i < N; ++i) p[i] = i;
sort(p, p + N, [&](int u, int v) {
int B[105];
int R[105];
memset(B, 0, sizeof(B));
memset(R, 0, sizeof(R));
B[u] = B[v] = N;
playRound(B, R);
int ok0 = (R[u] > N);
int ok1 = (R[v] > N);
assert(ok0 != ok2);
return (ok0 ? 0 : 1);
});
for (int i = 0; i < N; ++i) P[p[i]] = i + 1;
}
}
//
//int main() {
// grader();
// return 0;
//}
//
//
//static void runGame(int F) {
// int i;
//
// scanf("%d %d",&N,&W);
// for (i=0;i<N;++i) {
// scanf("%d",&P[i]);
// }
//
// numQueries = 0;
// if (F == 1) {
// printf("%d\n", minValue(N, W));
// } else if (F == 2) {
// printf("%d\n", maxValue(N, W));
// } else if (F == 3) {
// printf("%d\n", greaterValue(N, W));
// } else if (F == 4) {
// int userP[105];
// allValues(N, W, userP);
// for (i=0;i<N;i++) {
// printf("%d ",userP[i]);
// }
// printf("\n");
// }
// printf("Made %d calls to playRound.\n", numQueries);
//}
//
//static void grader() {
// int i;
//
// int F, G;
// scanf("%d %d",&F,&G);
//
// for (i=0;i<G;i++) {
// runGame(F);
// }
//}
Compilation message
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:117:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid = lo + hi >> 1;
| ~~~^~~~
koala.cpp: In lambda function:
koala.cpp:140:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
140 | int mid = lo + hi >> 1;
| ~~~^~~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from koala.cpp:4:
koala.cpp: In lambda function:
koala.cpp:168:27: error: 'ok2' was not declared in this scope; did you mean 'ok1'?
168 | assert(ok0 != ok2);
| ^~~
koala.cpp:167:17: warning: unused variable 'ok1' [-Wunused-variable]
167 | int ok1 = (R[v] > N);
| ^~~
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:130:1: warning: control reaches end of non-void function [-Wreturn-type]
130 | }
| ^
koala.cpp: In lambda function:
koala.cpp:153:9: warning: control reaches end of non-void function [-Wreturn-type]
153 | });
| ^
