#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 / 12;
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;
int r = 0;
for (int i = 2; i < N; ++i) B[i] = r;
playRound(B, R);
int ok0 = (R[0] > mid);
int ok1 = (R[1] > mid);
if (ok0 ^ ok1) return (ok0 ? 0 : 1);
// cout << lo << ' ' << hi << "aaaaa\n";
// cout << lo << ' ' << hi << ' ' << mid << ' ' << ok0 << ' ' << ok1 << '\n';
if (!ok0) hi = mid - 1;
else lo = mid + 1;
}
// return 0;
assert(0);
}
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.
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
//
//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;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
208 KB |
Output is correct |
| 2 |
Correct |
5 ms |
208 KB |
Output is correct |
| 3 |
Correct |
5 ms |
208 KB |
Output is correct |
| 4 |
Correct |
4 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
208 KB |
Output is correct |
| 2 |
Correct |
13 ms |
316 KB |
Output is correct |
| 3 |
Correct |
12 ms |
208 KB |
Output is correct |
| 4 |
Correct |
12 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
67 ms |
448 KB |
Output is partially correct |
| 2 |
Partially correct |
80 ms |
316 KB |
Output is partially correct |
| 3 |
Partially correct |
68 ms |
324 KB |
Output is partially correct |
| 4 |
Partially correct |
67 ms |
324 KB |
Output is partially correct |
| 5 |
Partially correct |
58 ms |
316 KB |
Output is partially correct |
| 6 |
Partially correct |
58 ms |
332 KB |
Output is partially correct |
| 7 |
Partially correct |
57 ms |
328 KB |
Output is partially correct |
| 8 |
Partially correct |
61 ms |
328 KB |
Output is partially correct |
| 9 |
Partially correct |
76 ms |
328 KB |
Output is partially correct |
| 10 |
Partially correct |
56 ms |
336 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
