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>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(x) (int) (x).size()
int minValue(int N, int W) {
int R[100], B[100];
for (int i = 0; i < 100; i++) B[i] = 0;
B[0] = 1;
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] == 0) return i;
}
return 0;
}
int maxValue(int N, int W) {
int B[100], R[100];
for (int i = 0; i < N; i++) {
B[i] = 1;
}
playRound(B, R);
vector<int> ps;
for (int i = 0; i < N; i++) {
if (R[i] == 2) ps.push_back(i);
}
for (int i = 0; i < N; i++) B[i] = 0;
for (int i = 0; i < 50; i++) B[ps[i]] = 2;
playRound(B, R);
ps.clear();
for (int i = 0; i < N; i++) {
if (R[i] == 3) ps.push_back(i);
}
for (int i = 0; i < N; i++) B[i] = 0;
for (int i = 0; i < 25; i++) B[ps[i]] = 4;
playRound(B, R);
ps.clear();
for (int i = 0; i < N; i++) {
if (R[i] == 5) ps.push_back(i);
}
for (int i = 0; i < N; i++) B[i] = 0;
for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] == 12) return i;
}
return 0;
}
mt19937 rnd(time(NULL));
int greaterValue(int N, int W) {
int B[100], R[100];
int L = 1, RG = 9;
while (L <= RG) {
int M = (L + RG) / 2;
B[0] = B[1] = M;
playRound(B, R);
if (R[0] > B[0] && R[1] > B[1]) L = M + 1;
else if (R[0] <= B[0] && R[1] <= B[1]) RG = M -1;
else {
return (R[0] < R[1]);
}
}
B[0] = B[1] = L;
playRound(B, R);
return R[0] < R[1];
}
struct xd {
pair<int, int> vals_seg;
vector<int> poss;
};
void allValues(int N, int W, int *P) {
int B[100], R[100];
vector<xd> lol;
vector<int> ap(N);
iota(all(ap), 0);
lol.pb({{1, N}, ap});
while (lol.size() < N) {
//cout << "yep" << endl;
vector<xd> new_lol;
for (int i = 0; i < sz(lol); i++) {
if (lol[i].poss.size() == 1) {
new_lol.pb(lol[i]);
continue;
}
int l = lol[i].vals_seg.first, r = lol[i].vals_seg.second;
int sm = 0;
for (int j = l; j <= r; j++) sm += j;
bool good = false;
pair<int, int> cs;
for (int cost = 1; cost * (r - l + 1) <= W; cost++) {
if (good) break;
for (int c2 = 0; c2 * (l - 1) + cost * (r - l + 1) <= W && (l != 1 || c2 <= 0); c2++) {
if (good) break;
int cntif0 = min(l - 1, (W - (N - r)) / (c2 + 1));
int cntifall = min(l - 1, max(0, ((W - (N - r)) - (cost + 1) * (r - l + 1)) / (c2 + 1)));
int currans = max((2 * l - 1 - cntif0) * cntif0 / 2, sm + (2 * l - 1 - cntifall) * cntifall / 2);
if ((r - l + 1) * (cost + 1) + N - r > W) {
currans = (2 * l - 1 - cntif0) * cntif0 / 2;
}
for (int newcnt = 1; newcnt < r - l + 1; newcnt++) {
int curcnt = min(l - 1, max(0, ((W - (N - r)) - newcnt * (cost + 1)) / (c2 + 1)));
if (currans < (2 * r - newcnt + 1) * newcnt / 2 + (2 * l - 1 - curcnt) * curcnt / 2) {
cs = {cost, c2};
good = true;
break;
}
}
}
}
for (int j = 0; j < 100; j++) {
B[j] = 0;
}
for (int j = 0; j < i; j++) {
for (int pos : lol[j].poss) B[pos] = cs.second;
}
for (int pos : lol[i].poss) B[pos] = cs.first;
playRound(B, R);
vector<int> highs, lows;
for (int pos : lol[i].poss) {
if (R[pos] > B[pos]) highs.pb(pos);
else lows.pb(pos);
}
new_lol.pb({{lol[i].vals_seg.first, lol[i].vals_seg.first + lows.size() - 1}, lows});
new_lol.pb({{lol[i].vals_seg.first + lows.size(), lol[i].vals_seg.second}, highs});
}
swap(new_lol, lol);
}
for (int i = 0; i < N; i++) {
P[lol[i].poss[0]] = i + 1;
}
}
Compilation message (stderr)
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
| ~~^~~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:85:27: warning: comparison of integer expressions of different signedness: 'std::vector<xd>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
85 | while (lol.size() < 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... |