#include "koala.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
typedef long long llong;
const int MAXN = 128;
const int INF = 1e9;
int n, w;
int __b[MAXN];
int __r[MAXN];
std::vector <int> play(const std::vector <int> &b)
{
assert(b.size() == n);
for (int i = 0 ; i < n ; ++i)
{
__b[i] = b[i];
}
playRound(__b, __r);
std::vector <int> r(n);
for (int i = 0 ; i < n ; ++i)
{
r[i] = __r[i];
}
return r;
}
int minValue(int N, int W)
{
n = N; w = W;
std::vector <int> askFor(n, 0);
askFor[0] = 1;
std::vector <int> r = play(askFor);
for (int i = 0 ; i < N ; ++i)
{
if (r[i] == 0)
{
return i;
}
}
// 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)
{
n = N; w = W;
int step = 1;
std::vector <int> candidates(n);
std::iota(candidates.begin(), candidates.end(), 0);
while (candidates.size() > 1)
{
std::vector <int> b(n, 0);
for (const int &pos : candidates)
{
b[pos] = w / candidates.size();
}
// step = 2 * step;
std::vector <int> r = play(b);
std::vector <int> newCandidates;
for (const int &pos : candidates)
{
if (r[pos] > b[pos])
{
newCandidates.push_back(pos);
}
}
candidates = newCandidates;
}
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return candidates[0];
}
bool cmp(int x, int y)
{
int times = 0;
int l = 1, rr = 9, mid;
while (l + 1 < rr)
{
times++;
mid = l + (rr - l + 1) / 2 + (r - l == 8);
std::vector <int> b(n, 0);
b[x] = b[y] = mid;
std::vector <int> r = play(b);
if (r[x] > b[x] && r[y] <= b[y]) return false;
if (r[y] > b[y] && r[x] <= b[x]) return true;
if (r[x] <= b[x]) rr = mid;
else l = mid;
}
std::vector <int> b(n, 0);
b[x] = b[y] = 1;
std::vector <int> r = play(b);
if (r[x] > b[x] && r[y] <= b[y]) return false;
if (r[y] > b[y] && r[x] <= b[x]) return true;
assert(false);
}
int greaterValue(int N, int W)
{
n = N; w = W;
// n = N; w = W;
// std::vector <int> toAsk(n, 0);
// toAsk[0] = toAsk[1] = 1;
// std::vector <int> r = play(toAsk);
// if ()
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return cmp(0, 1);
}
bool sigmaCMP(int x, int y)
{
std::vector <int> b(n, 0);
b[x] = b[y] = w / 2;
std::vector <int> r = play(b);
if (r[x] > n) return false;
return true;
}
int toSort[MAXN];
int cpy[MAXN];
void sigmaMerge(int l, int r)
{
if (l == r)
{
return;
}
int mid = (l + r) / 2;
sigmaMerge(l, mid);
sigmaMerge(mid + 1, r);
int lPtr = l, rPtr = mid + 1, ptr = l;
while (lPtr <= mid || rPtr <= r)
{
if (lPtr == mid + 1)
{
cpy[ptr++] = toSort[rPtr++];
continue;
}
if (rPtr == r + 1)
{
cpy[ptr++] = toSort[lPtr++];
continue;
}
if (sigmaCMP(toSort[lPtr], toSort[rPtr]))
{
cpy[ptr++] = toSort[lPtr++];
} else
{
cpy[ptr++] = toSort[rPtr++];
}
}
for (int i = l ; i <= r ; ++i)
{
toSort[i] = cpy[i];
}
}
void merge(int l, int r)
{
if (l == r)
{
return;
}
int mid = (l + r) / 2;
merge(l, mid);
merge(mid + 1, r);
int lPtr = l, rPtr = mid + 1, ptr = l;
while (lPtr <= mid || rPtr <= r)
{
if (lPtr == mid + 1)
{
cpy[ptr++] = toSort[rPtr++];
continue;
}
if (rPtr == r + 1)
{
cpy[ptr++] = toSort[lPtr++];
continue;
}
if (cmp(toSort[lPtr], toSort[rPtr]))
{
cpy[ptr++] = toSort[lPtr++];
} else
{
cpy[ptr++] = toSort[rPtr++];
}
}
for (int i = l ; i <= r ; ++i)
{
toSort[i] = cpy[i];
}
}
std::mt19937 rng(69420);
void allValues(int N, int W, int *res)
{
n = N; w = W;
if (W == 2*N)
{
std::iota(toSort, toSort + n, 0);
sigmaMerge(0, n - 1);
for (int i = 0 ; i < n ; ++i)
{
res[toSort[i]] = i + 1;
}
} else {
std::iota(toSort, toSort + n, 0);
std::shuffle(toSort, toSort + n, rng);
merge(0, n - 1);
for (int i = 0 ; i < n ; ++i)
{
res[toSort[i]] = i + 1;
}
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from koala.cpp:5:
koala.cpp: In function 'std::vector<int> play(const std::vector<int>&)':
koala.cpp:18:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
18 | assert(b.size() == n);
| ~~~~~~~~~^~~~
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:58:9: warning: unused variable 'step' [-Wunused-variable]
58 | int step = 1;
| ^~~~
koala.cpp: In function 'bool cmp(int, int)':
koala.cpp:96:40: error: 'r' was not declared in this scope; did you mean 'rr'?
96 | mid = l + (rr - l + 1) / 2 + (r - l == 8);
| ^
| rr
