#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
int minValue(int N, int W) {
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
int b[N], r[N];
memset(b, 0, sizeof(b)); b[0] = 1;
playRound(b, r);
if (r[0] <= 1) {
// he couldnt care less to take this
return 0;
}
// he could sad
for (int i = 1; i < N; i++) {
if (r[i] == 0) return i;
}
}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
vector<int> possible(N);
iota(begin(possible), end(possible), 0);
int b[N], r[N];
while (possible.size() > 1) {
int add = W / possible.size();
memset(b, 0, sizeof(b));
for (auto& i : possible) b[i] = add;
playRound(b, r);
possible.clear();
for (int i = 0; i < N; i++) if (r[i] > add) possible.push_back(i);
}
return possible[0];
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
int b[N], R[N];
memset(b, 0, sizeof(b));
int l = 1, r = 13;
while (l <= r) {
int mid = (l + r) >> 1;
b[0] = mid, b[1] = mid;
playRound(b, R);
if (min(R[0], R[1]) > mid /*he took both so idk*/) l = mid + 1;
else if (max(R[0], R[1]) <= mid /*he took neither so spend less lol*/) r = mid - 1;
else {
if (R[0] < R[1]) return 1;
else return 0;
}
}
assert(false);
}
vector<int> ind;
int n, w;
bool compare(int i, int j) {
// is i < j?
int b[n], r[n];
memset(b, 0, sizeof(b));
b[i] = w / 2, b[j] = w / 2;
playRound(b, r);
return (r[j] * 2) > w;
}
vector<int> merge_sort(int l, int r) {
if (l == r) return vector<int>(1, l);
int mid = (l + r) >> 1;
auto left = merge_sort(l, mid), right = merge_sort(mid + 1, r);
vector<int> ret;
int i = 0, j = 0;
while (i < left.size() && j < right.size()) {
if (compare(left[i], right[j])) ret.push_back(left[i++]);
else ret.push_back(right[j++]);
}
while (i < left.size()) ret.push_back(left[i++]);
while (j < right.size()) ret.push_back(right[j++]);
return ret;
}
void allValues(int N, int W, int *P) {
n = N, w = W;
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
ind.resize(N);
iota(begin(ind), end(ind), 0LL);
auto ans = merge_sort(0, N - 1);
for (int i = 0; i < N; i++) P[ans[i]] = i + 1;
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
Compilation message
koala.cpp: In function 'std::vector<int> merge_sort(int, int)':
koala.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while (i < left.size() && j < right.size()) {
| ~~^~~~~~~~~~~~~
koala.cpp:80:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while (i < left.size() && j < right.size()) {
| ~~^~~~~~~~~~~~~~
koala.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | while (i < left.size()) ret.push_back(left[i++]);
| ~~^~~~~~~~~~~~~
koala.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (j < right.size()) ret.push_back(right[j++]);
| ~~^~~~~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
20 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
344 KB |
Output is correct |
| 3 |
Correct |
3 ms |
344 KB |
Output is correct |
| 4 |
Correct |
3 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
344 KB |
Output is correct |
| 2 |
Correct |
10 ms |
344 KB |
Output is correct |
| 3 |
Correct |
10 ms |
452 KB |
Output is correct |
| 4 |
Correct |
10 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
728 KB |
Output is correct |
| 2 |
Correct |
39 ms |
460 KB |
Output is correct |
| 3 |
Correct |
33 ms |
472 KB |
Output is correct |
| 4 |
Correct |
34 ms |
472 KB |
Output is correct |
| 5 |
Correct |
36 ms |
476 KB |
Output is correct |
| 6 |
Correct |
35 ms |
468 KB |
Output is correct |
| 7 |
Correct |
34 ms |
488 KB |
Output is correct |
| 8 |
Correct |
38 ms |
476 KB |
Output is correct |
| 9 |
Correct |
33 ms |
476 KB |
Output is correct |
| 10 |
Correct |
36 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
344 KB |
Output is correct |
| 2 |
Correct |
26 ms |
344 KB |
Output is correct |
| 3 |
Correct |
25 ms |
452 KB |
Output is correct |
| 4 |
Correct |
25 ms |
344 KB |
Output is correct |
| 5 |
Correct |
24 ms |
344 KB |
Output is correct |
| 6 |
Correct |
25 ms |
344 KB |
Output is correct |
| 7 |
Correct |
24 ms |
456 KB |
Output is correct |
| 8 |
Correct |
24 ms |
344 KB |
Output is correct |
| 9 |
Correct |
24 ms |
448 KB |
Output is correct |
| 10 |
Correct |
24 ms |
344 KB |
Output is correct |
| 11 |
Correct |
25 ms |
448 KB |
Output is correct |
| 12 |
Correct |
20 ms |
344 KB |
Output is correct |
| 13 |
Correct |
25 ms |
448 KB |
Output is correct |
| 14 |
Correct |
35 ms |
344 KB |
Output is correct |
| 15 |
Correct |
23 ms |
448 KB |
Output is correct |
| 16 |
Correct |
22 ms |
452 KB |
Output is correct |
| 17 |
Correct |
21 ms |
448 KB |
Output is correct |
| 18 |
Correct |
23 ms |
344 KB |
Output is correct |
| 19 |
Correct |
22 ms |
344 KB |
Output is correct |
| 20 |
Correct |
22 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
