// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "koala.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 110, mod = 1e9 + 7, inf = 1e9 + 10;
int minValue(int N, int W) {
int A[maxn], B[maxn];
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
A[0] = 1;
playRound(A, B);
if(B[0] <= 1)
return 0;
int ans = 0;
for(int i = 1; i < N; i++)
if(B[i] == 0)
ans = i;
return ans;
}
int maxValue(int N, int W) {
int SM[maxn];
vector<pii> v[maxn];
int h[maxn];
pii pr[maxn];
memset(SM, 0, sizeof SM);
memset(h, -1, sizeof h);
for(int i = 0; i < maxn; i++)
v[i].clear();
for(int i = 1; i <= N; i++)
SM[i] = SM[i-1] + i;
auto f = [&](int n, int cost, int top, int lim){
assert(top <= n);
int sm = 0, bst = 0;
for(int i = 0; i <= top; i++){
if(i * cost > lim)
break;
bst = max(bst, sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))]);
sm+= n-i;
}
sm = 0;
int bstid = -1;
for(int i = 0; i <= top; i++){
if(i * cost > lim)
break;
int num = sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))];
if(num == bst){
if(bstid == -1)
bstid = i;
if(bstid != i)
return -1;
}
sm+= n-i;
}
return bstid;
};
for(int top = 100; top >= 1; top--){
for(int cost = 2; top * (cost-1) <= 100; cost++){
int x = f(100, cost, top, 100);
if(x != -1)
v[top].PB({x, cost});
}
}
queue<int> q;
h[N] = 0;
q.push(N);
while(sz(q)){
int u = q.front();
q.pop();
for(pii p : v[u])
if(h[p.F] == -1)
pr[p.F] = {u, p.S}, h[p.F] = h[u] + 1, q.push(p.F);
}
vector<pii> tdo;
int tmp = 1;
while(tmp != N){
tdo.PB(pr[tmp]);
tmp = pr[tmp].F;
}
reverse(tdo.begin(), tdo.end());
vector<int> big;
for(int i = 0; i < N; i++){
big.PB(i);
}
int A[maxn], B[maxn];
bool inside[maxn];
for(pii p : tdo){
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
memset(inside, 0, sizeof inside);
for(int id : big)
A[id] = p.S-1, inside[id] = 1;
playRound(A, B);
big.clear();
for(int i = 0; i < N; i++){
if(inside[i] && B[i] >= p.S)
big.PB(i);
}
}
assert(sz(big) == 1);
return big[0];
}
bool comp(int a, int b){
int A[maxn], B[maxn];
for(int d : {9, 5, 3, 1}){
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
A[a] = d, A[b] = d;
playRound(A, B);
bool X = B[a] > d, Y = B[b] > d;
if(X ^ Y){
if(X)
return 0;
else
return 1;
}
}
assert(0);
}
int greaterValue(int N, int W) {
return comp(0, 1);
}
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.
} else {
int A[maxn], B[maxn];
for(int i = 0; i < N; i++)
P[i] = 0;
memset(A, 0, sizeof A);
fill(A, A+N, 1);
playRound(A, B);
set<int> big;
vector<int> vec, del;
for(int i = 0; i < N; i++){
if(B[i] > 1)
big.insert(i), vec.PB(i);
}
int NXT = N/2;
while(sz(vec) > 1){
del.PB(vec.back());
vec.pop_back();
del.PB(vec.back());
vec.pop_back();
for(int i = 0; i < N; i++)
A[i] = 1;
for(int i : del)
A[i] = 0;
playRound(A, B);
for(int i = 0; i < N; i++){
if(big.count(i) == 0 && B[i] > A[i])
big.insert(i), vec.PB(i), P[i] = NXT, NXT--;
}
}
assert(sz(vec) == 1 && sz(big) == N-1 && NXT == 1);
for(int i = 0; i < N; i++){
if(big.count(i) == 0)
P[i] = 1;
}
int SM[maxn];
SM[0] = 0;
for(int i = 1; i < maxn; i++)
SM[i] = i + SM[i-1];
pii can[maxn];
auto f = [&](int n, int k, int w){
int sm = 0;
pii bst = {0, 0};
int ID = 0;
for(int i = 0; i <= k && i * w <= n; i++){
int cnt = min(n - k, n - w*i);
pii _ = bst;
bst = max(bst, (pii){sm + SM[n-k] - SM[n-k-cnt], cnt + i});
if(_ != bst)
ID = i;
sm+= n-i;
}
return ID;
};
fill(can + 1, can + N + 1, (pii){-1, -1});
for(int i = 1; i <= N; i++){
for(int j = 2; i*j <= W; j++){
int x = f(N, i, j);
if(x < i)
can[x+1] = {i, j};
}
}
for(int i = (N/2); i >= 2; i--){
memset(A, 0, sizeof A);
int k = can[i].F, w = can[i].S;
assert(k != -1);
for(int j = 0; j < N; j++){
if((P[j] == 0) || (N+1-P[j] <= k))
A[j] = w-1;
}
playRound(A, B);
for(int j = 0; j < N; j++){
if(P[j] == 0 && A[j] >= B[j])
P[j] = N+1-i;
}
}
for(int i = 0; i < N; i++){
if(P[i] == 0)
P[i] = N;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
512 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
384 KB |
Output is correct |
| 2 |
Correct |
24 ms |
384 KB |
Output is correct |
| 3 |
Correct |
28 ms |
384 KB |
Output is correct |
| 4 |
Correct |
23 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
77 ms |
384 KB |
Output is partially correct |
| 2 |
Partially correct |
79 ms |
384 KB |
Output is partially correct |
| 3 |
Partially correct |
74 ms |
384 KB |
Output is partially correct |
| 4 |
Partially correct |
79 ms |
384 KB |
Output is partially correct |
| 5 |
Partially correct |
72 ms |
384 KB |
Output is partially correct |
| 6 |
Correct |
70 ms |
384 KB |
Output is correct |
| 7 |
Partially correct |
71 ms |
384 KB |
Output is partially correct |
| 8 |
Correct |
70 ms |
384 KB |
Output is correct |
| 9 |
Correct |
69 ms |
384 KB |
Output is correct |
| 10 |
Correct |
71 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
