#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
vector<bool> simulate(vector<int> P, vector<int> B, int N, int W) {
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);
}
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;
vector<bool> take(N);
for (i = N - 1; i >= 0; --i) {
take[i] = taken[i][cur];
int R = taken[i][cur] ? (B[i] + 1) : 0;
cur -= R;
}
return take;
}
using ll = long long;
bool doesSeparate(int N, int W, int x, int i, int j) {
vector<int> other;
for (int k = 1; k <= N; ++k)
if (i != k and j != k)
other.push_back(k);
reverse(other.begin(), other.end());
array<array<ll, 2>, 2> sol;
for (int p = 0; p < 2; ++p)
sol[p].fill(0);
for (int take0 = 0; take0 < 2; ++take0)
for (int take1 = 0; take1 < 2; ++take1) {
int restant = W - (x + 1) * (take0 + take1);
if (restant < 0)
continue;
sol[take0][take1] = i * take0 + j * take1;
for (int k = 0; k < restant and k < (int)other.size(); ++k)
sol[take0][take1] += other[k];
}
int best = max({sol[0][0], sol[0][1], sol[1][0], sol[1][1]});
return best == sol[0][1] or best == sol[1][0];
}
int minValue(int N, int W) {
vector<int> b(N);
b[0] = 1;
vector<int> r(N);
playRound(b.data(), r.data());
for (int i = 0; i < N; ++i)
if (b[i] >= r[i])
return i;
assert(false);
}
int maxValue(int N, int W) {
vector<int> candidats(N);
iota(candidats.begin(), candidats.end(), 0);
while (candidats.size() > 1) {
int nbCandidats = candidats.size();
vector<int> b(N);
for (int u : candidats)
b[u] = W / nbCandidats;
vector<int> r(N);
playRound(b.data(), r.data());
;
vector<int> nxt;
for (int u : candidats)
if (b[u] < r[u])
nxt.push_back(u);
candidats = nxt;
}
assert(!candidats.empty());
return candidats[0];
return 0;
}
bool separates[51][101][101];
void initGreaterValue() {
static bool initialized = false;
if (!initialized) {
initialized = true;
for (int x = 1; x <= 50; ++x)
for (int i = 1; i <= 100; ++i)
for (int j = i + 1; j <= 100; ++j)
separates[x][i][j] = doesSeparate(100, 100, x, i, j);
}
}
int greaterValue(int N, int W) {
initGreaterValue();
vector<pair<int, int>> candidats;
for (int i = 1; i <= N; ++i)
for (int j = i + 1; j <= N; ++j)
candidats.emplace_back(i, j);
while (true) {
int bestX = -1;
int largest = 0;
for (int x = 1; x <= W / 2; ++x) {
int cnt = 0;
for (auto [i, j] : candidats)
if (separates[x][i][j])
cnt++;
if (largest < cnt)
largest = cnt, bestX = x;
}
int x = bestX;
vector<int> b(N), r(N);
b[0] = b[1] = x;
playRound(b.data(), r.data());
int take0 = b[0] < r[0];
int take1 = b[1] < r[1];
dbg(x, take0, take1);
if (take0 == take1) {
vector<pair<int, int>> nxtCandidats;
for (auto [i, j] : candidats)
if (!separates[x][i][j])
nxtCandidats.emplace_back(i, j);
candidats = nxtCandidats;
} else if (take0)
return 0;
else
return 1;
}
}
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.
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
208 KB |
Output is correct |
| 3 |
Correct |
4 ms |
208 KB |
Output is correct |
| 4 |
Correct |
3 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
208 KB |
Output is correct |
| 2 |
Correct |
10 ms |
320 KB |
Output is correct |
| 3 |
Correct |
10 ms |
328 KB |
Output is correct |
| 4 |
Correct |
10 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
552 ms |
952 KB |
Output is partially correct |
| 2 |
Partially correct |
533 ms |
936 KB |
Output is partially correct |
| 3 |
Partially correct |
549 ms |
840 KB |
Output is partially correct |
| 4 |
Partially correct |
549 ms |
948 KB |
Output is partially correct |
| 5 |
Partially correct |
551 ms |
840 KB |
Output is partially correct |
| 6 |
Correct |
556 ms |
1048 KB |
Output is correct |
| 7 |
Partially correct |
555 ms |
1096 KB |
Output is partially correct |
| 8 |
Correct |
551 ms |
848 KB |
Output is correct |
| 9 |
Correct |
550 ms |
892 KB |
Output is correct |
| 10 |
Correct |
553 ms |
1060 KB |
Output is 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 |
- |
