#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;
// returns such i that we get [i, r], [l, i - 1]
int put(int l, int r, int x = -1) {
const int n = 100;
if (x == -1) {
x = n / (r - l + 1);
}
int at = r + 1, cost = 0, sum = 0, cnt = 0;
int best = r + 1;
pair<int, int> mx = { -1, -1 };
while (at > l && cost + x + 1 <= n) {
at--;
sum += at;
cnt++;
cost += x + 1;
}
vector<int> other;
for (int i = n; i >= 1; i--) {
if (i < l || r < i) other.push_back(i);
}
int pos = -1;
while (pos + 1 < other.size() && cost < n) {
pos++;
cost++;
cnt++;
sum += other[pos];
}
if (mx < make_pair(sum, cnt))
mx = { sum, cnt }, best = at;
while (at <= r) {
cost -= x + 1;
sum -= at;
cnt--;
at++;
while (pos + 1 < other.size() && cost < n) {
pos++;
cost++;
cnt++;
sum += other[pos];
}
if (mx < make_pair(sum, cnt))
mx = { sum, cnt }, best = at;
}
return best;
}
int nn;
void playRound(int *B, int *R);
/*
void playRound(int *B, int *R) {
cout << "B: ";
for (int i = 0; i < nn; i++) cout << B[i] << " "; cout << '\n';
cout << "R: ";
for (int i = 0; i < nn; i++) cin >> R[i];
}
*/
int B[105], R[105];
void clear() {
for (int i = 0; i < nn; i++) B[i] = 0;
}
void play() {
playRound(B, R);
}
vector<int> atleast(int k) {
vector<int> rtn;
for (int i = 0; i < nn; i++)
if (R[i] >= k) rtn.push_back(i);
return rtn;
}
vector<int> atmost(int k) {
vector<int> rtn;
for (int i = 0; i < nn; i++)
if (R[i] <= k) rtn.push_back(i);
return rtn;
}
int minValue(int n, int w) {
nn = n;
clear();
B[0] = 1;
play();
vector<int> pos = atmost(0);
if (pos.size()) return pos[0];
return 0;
}
int maxValue(int n, int w) {
nn = n;
vector<int> prev, cur;
for (int i = 0; i < n; i++) prev.push_back(i);
while (prev.size() > 1) {
clear();
int val = n / int(prev.size());
for (const auto &i : prev) B[i] = val;
play();
cur = atleast(1 + val);
vector<int> cut;
int p1 = 0, p2 = 0;
while (p1 < prev.size() && p2 < cur.size()) {
if (prev[p1] == cur[p2]) cut.push_back(prev[p1]), p1++, p2++;
else if (prev[p1] < cur[p2]) p1++;
else p2++;
}
prev = cut;
}
return prev[0];
}
int greaterValue(int n, int w) {
nn = n;
int lo = 1, hi = 8, mid;
while (lo < hi) {
mid = (lo + hi) / 2;
clear();
B[0] = B[1] = mid;
play();
if (R[0] > mid && R[1] > mid) lo = mid + 1;
else hi = mid;
}
clear();
B[0] = B[1] = lo;
play();
if (B[0] > lo) return 0;
return 1;
}
bool cmp(int x, int y) {
clear();
B[x] = B[y] = 100;
play();
if (R[x] > 100) return false;
return true;
}
int arr1[105], arr2[105];
void mergesort(vector<int> &a, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
int sz1 = 0, sz2 = 0, p1 = 0, p2 = 0;
for (int i = l; i <= mid; i++)
arr1[sz1++] = a[i];
for (int i = mid + 1; i <= r; i++)
arr2[sz2++] = a[i];
while (p1 < sz1 && p2 < sz2) {
if (cmp(arr1[p1], arr2[p2])) a[l + p1 + p2] = arr1[p1], p1++;
else a[l + p1 + p2] = arr2[p2], p2++;
}
while (p1 < sz1)
a[l + p1 + p2] = arr1[p1], p1++;
while (p2 < sz2)
a[l + p1 + p2] = arr2[p2], p2++;
}
void allValues(int n, int w, int *P) {
nn = n;
if (w == 2 * n) {
vector<int> p;
for (int i = 0; i < n; i++) p.push_back(i);
mergesort(p, 0, n - 1);
for (int i = 0; i < n; i++)
P[p[i]] = 1 + i;
return;
}
else {
}
}
/*
int main() {
int ans[105];
int n;
cin >> n;
}
*/
Compilation message
koala.cpp: In function 'int put(int, int, int)':
koala.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pos + 1 < other.size() && cost < n) {
~~~~~~~~^~~~~~~~~~~~~~
koala.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pos + 1 < other.size() && cost < n) {
~~~~~~~~^~~~~~~~~~~~~~
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:115:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p1 < prev.size() && p2 < cur.size()) {
~~~^~~~~~~~~~~~~
koala.cpp:115:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (p1 < prev.size() && p2 < cur.size()) {
~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
384 KB |
Output is correct |
| 2 |
Correct |
17 ms |
384 KB |
Output is correct |
| 3 |
Correct |
22 ms |
384 KB |
Output is correct |
| 4 |
Correct |
14 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
384 KB |
Output is correct |
| 2 |
Correct |
36 ms |
512 KB |
Output is correct |
| 3 |
Correct |
32 ms |
356 KB |
Output is correct |
| 4 |
Correct |
32 ms |
384 KB |
Output is correct |
| 5 |
Correct |
31 ms |
384 KB |
Output is correct |
| 6 |
Correct |
35 ms |
384 KB |
Output is correct |
| 7 |
Correct |
29 ms |
384 KB |
Output is correct |
| 8 |
Correct |
28 ms |
384 KB |
Output is correct |
| 9 |
Correct |
33 ms |
384 KB |
Output is correct |
| 10 |
Correct |
27 ms |
384 KB |
Output is correct |
| 11 |
Correct |
35 ms |
384 KB |
Output is correct |
| 12 |
Correct |
19 ms |
384 KB |
Output is correct |
| 13 |
Correct |
30 ms |
384 KB |
Output is correct |
| 14 |
Correct |
27 ms |
384 KB |
Output is correct |
| 15 |
Correct |
27 ms |
384 KB |
Output is correct |
| 16 |
Correct |
28 ms |
432 KB |
Output is correct |
| 17 |
Correct |
27 ms |
512 KB |
Output is correct |
| 18 |
Correct |
27 ms |
384 KB |
Output is correct |
| 19 |
Correct |
25 ms |
384 KB |
Output is correct |
| 20 |
Correct |
26 ms |
392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
