This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "koala.h"
#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define pb push_back
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 n = N;
int a[n], b[n];
memset(a, 0, sizeof(a));
a[0] = 1;
playRound(a, b);
for(int i = 0; i < n; ++i) {
if(b[i] == 0) {
return i;
}
}
return 0;
}
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.
int n = N, a[n], b[n];
vector<int> v;
for(int i = 0; i < n; ++i) {
v.pb(i);
}
while(sz(v) > 1) {
int t = W / sz(v);
bool used[n];
memset(used, 0, sizeof(used));
for(auto x : v) used[x] = 1;
for(int i = 0; i < n; ++i) {
if(!used[i]) {
a[i] = 0;
} else {
a[i] = t;
}
}
playRound(a, b);
vector<int> to;
for(int i = 0; i < n; ++i) {
if(b[i] > t) {
to.pb(i);
}
}
v = to;
}
return v[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 n = N, a[n], b[n];
int l = 1, r = min(9, W / 2), ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
memset(a, 0, sizeof(a));
a[0] = a[1] = mid;
playRound(a, b);
if(a[0] >= b[0] && a[1] >= b[1]) {
r = mid - 1;
continue;
}
bool c = (a[0] < b[0]), d = (a[1] < b[1]);
if(c && d) {
l = mid + 1;
continue;
}
ans = (c < d);
break;
}
assert(ans != -1);
return ans;
}
bool comp(int i, int j, int n) {
int a[n], b[n];
memset(a, 0, sizeof(a));
a[i] = a[j] = n;
playRound(a, b);
assert((b[i] > a[i]) || (b[j] > a[j]));
if(b[i] < a[i]) {
return 1;
}
return 0;
}
void calc(int l, int r, vector<int> &v, vector<int> &temp) {
if(l == r) {
return;
}
int mid = (l + r) >> 1;
calc(l, mid, v, temp);
calc(mid + 1, r, v, temp);
int timer = l, i = l, j = mid + 1;
while(i <= mid && j <= r) {
if(comp(v[i], v[j], sz(v))) {
temp[timer++] = v[i++];
continue;
}
temp[timer++] = v[j++];
}
for(int k = i; k <= mid; ++k) temp[timer++] = v[k];
for(int k = j; k <= r; ++k) temp[timer++] = v[k];
for(int i = l; i <= r; ++i) v[i] = temp[i];
}
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.
int n = N;
vector<int> v, p;
for(int i = 1; i <= n; ++i) {
v.pb(i - 1);
}
p = v;
calc(0, n - 1, v, p);
for(int i = 0; i < n; ++i) {
P[v[i]] = i + 1;
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
int n = N, a[n], b[n];
vector<int> v;
for(int t = 0; t < n; ++t) {
}
for(int i = 0; i < n; ++i) {
P[v[i]] = i + 1;
}
}
}
Compilation message (stderr)
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:137:14: warning: unused variable 'a' [-Wunused-variable]
137 | int n = N, a[n], b[n];
| ^
koala.cpp:137:20: warning: unused variable 'b' [-Wunused-variable]
137 | int n = N, a[n], b[n];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |