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 <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
int cache[2][205];
int num[2][205];
char taken[105][205];
const int N = 100;
int W = 200;
int b[N], r[N], tk[N], val[N];
void solve() {
int i, j;
for (i=0;i<205;++i) {
cache[1][i] = 0;
num[1][i] = 0;
}
for (i=0;i<N;++i) {
int v = b[i]+1;
int ii = i&1;
int o = ii^1;
for (j=0;j<=W;++j) {
cache[ii][j] = cache[o][j];
num[ii][j] = num[o][j];
taken[i][j] = 0;
}
for (j=W;j>=v;--j) {
int h = cache[o][j-v] + val[i];
int hn = num[o][j-v] + 1;
if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
cache[ii][j] = h;
num[ii][j] = hn;
taken[i][j] = 1;
} else {
taken[i][j] = 0;
}
}
}
int cur = W;
for (i=N-1;i>=0;--i) {
int cr = taken[i][cur] ? (b[i] + 1) : 0;
cur -= cr;
if (cr)
tk[i] = 1;
else
tk[i] = 0;
}
}
int minValue(int n, int w) {
b[0] = 1;
playRound(b, r);
rep(i, n)
if (r[i] <= b[i])
return i;
return 0;
}
int maxValue(int n, int w) {
vector<int> a(n), na;
rep(i, n)
a[i] = i;
while (a.size() > 1) {
int cw = w / a.size();
rep(i, n)
b[i] = 0;
for (int i : a)
b[i] = cw;
playRound(b, r);
na.clear();
for (int i : a)
if (r[i] > cw)
na.push_back(i);
a = na;
}
assert(!a.empty());
return a[0];
}
int greaterValue(int n, int w) {
int l = 0, rr = 6, m;
vector<int> a {1, 2, 3, 4, 5, 6, 8};
while (1) {
m = (l + rr) / 2;
b[0] = b[1] = a[m];
playRound(b, r);
if (r[0] > a[m] && r[1] > a[m]) {
assert(l != rr);
l = m + 1;
}
else if (r[0] <= a[m] && r[1] <= a[m]) {
assert(l != rr);
rr = m - 1;
}
else
return r[0] < r[1];
}
return -1;
}
void go(int l, int cr, vector<int> lp) {
// cout << l << ' '<< cr << endl;
if (cr - l <= 1)
return;
rep(i, N)
b[i] = 0;
for (int i : lp)
b[i] = W / lp.size();
while (1) {
assert(b[lp[0]] > 0);
solve();
if (tk[lp[0]] != tk[lp.back()]) {
playRound(b, r);
vector<int> l1, l2;
int c1 = l;
for (int i : lp) {
if (r[i] > b[i])
l2.push_back(i);
else
l1.push_back(i);
}
assert(!l1.empty() && !l2.empty());
for (int i : l1)
val[i] = c1++;
for (int i : l2)
val[i] = c1++;
go(l + l1.size(), cr, l2);
go(l, l + l1.size(), l1);
return;
}
for (int i : lp)
b[i]--;
}
}
void allValues(int n, int w, int *p) {
W = w;
rep(i, n)
val[i] = i + 1;
vector<int> lp(n);
rep(i, n)
lp[i] = i;
go(1, n + 1, lp);
rep(i, n)
p[i] = val[i];
if (w == 2*n) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
# | 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... |