Submission #268117

#	Time	Username	Problem	Language	Result	Execution time	Memory
268117		shayan_p	Koala Game (APIO17_koala)	C++14	100 / 100	91 ms	516 KiB

koala

// 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];
    int L = 1, R = 9;
    while(true){
	int d = (L+R) >> 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;
	}
	if(X && Y)
	    L = d+1;
	else
	    R = d-1;
    }
    assert(0);
}

int greaterValue(int N, int W) {
    return comp(0, 1);
}

int magic[maxn][maxn];

void go(int l, int r, vector<int> vec, int *P){
    int A[maxn], B[maxn];    
    if(r-l == 1){
	P[vec.back()] = l;
	return;
    }
    memset(A, 0, sizeof A);
    for(int x : vec){
	A[x] = magic[l][r];
    }
    playRound(A, B);
    vector<int> v1, v2;
    for(int i : vec){
	if(A[i] >= B[i])
	    v1.PB(i);
	else
	    v2.PB(i);				 
    }
    assert(!v1.empty() && !v2.empty());
    go(l, l + sz(v1), v1, P);
    go(l + sz(v1), r, v2, P);
}

void allValues(int N, int W, int *P) {
    int SM[maxn];
    SM[0] = 0;
    for(int i = 1; i < maxn; i++)
	SM[i] = SM[i-1] + i;
    auto f = [&](int l, int r, int cost){
		 pii bst = {-1, 0};
		 int ret = -1;
		 for(int i = r; i >= l && (r-i) * cost <= W; i--){
		     pii p = {SM[r-1] - SM[i], r-i};
		     int rst = W - (r-i) * cost;
		     if(rst <= N - r + 1)
			 p.S+= rst, p.F+= SM[N] - SM[N - rst];
		     else
			 rst-= (N-r+1), p.S+= (N-r+1), p.F+= SM[N] - SM[r-1];
		     rst = min(rst, l-1);
		     p.S+= rst, p.F+= SM[l-1] - SM[l-1-rst];

		     pii _ = bst;
		     bst = max(bst, p);
		     if(_ != bst)
			 ret = i;
		 }
		 return ret;
	     };
    for(int l = 1; l <= N; l++){
	for(int r = l+2; r <= N + 1; r++){
	    magic[l][r] = -1;
	    for(int cst = 1; cst * (r-l) <= W; cst++){
		int num = f(l, r, cst+1);
		if(num == -1){
		    P[0] = l, P[1] = r, P[2] = cst;
		    return;
		}
		    
		if(num != l && num != r){
		    magic[l][r] = cst;
		    break;
		}
	    }
	    assert(magic[l][r] != -1);
	}
    }
    vector<int> vec;
    for(int i = 0; i < N; i++)
	vec.PB(i);
    go(1, N + 1, vec, P);
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53