Submission #265039

#	Time	Username	Problem	Language	Result	Execution time	Memory
265039		shayan_p	Koala Game (APIO17_koala)	C++14	33 / 100	79 ms	512 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];
    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;
	}
    }
}

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