Submission #266866

#	Time	Username	Problem	Language	Result	Execution time	Memory
266866		amoo_safar	Koala Game (APIO17_koala)	C++17	0 / 100	184 ms	888 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

int minValue(int n, int w) {
    assert(n == w);
    return 0;
}

int maxValue(int n, int w) {
    assert(n == w);
    return 0;
}

int greaterValue(int n, int w) {
    assert(n == w);
    return 0;
}

int Sum(int l, int r){
    return (l + r) * (r - l + 1) / 2;;
}



int dp[102][102];
int inp[100], out[100];
int ans[100];

void Solve(vector<int> pos, int L, int R){
    if(L == R){
        ans[pos[0]] = L;
        return ;
    }
    int cnt = dp[L][R];
    memset(inp, 0, sizeof inp);
    for(auto x : pos)
        inp[x] = cnt;
    playRound(inp, out);
    vector<int> Le, Bi;
    for(int i = 0; i < 100; i++){
        if(inp[i] > 0){
            if(inp[i] < out[i]){
                Bi.pb(i);
            } else {
                Le.pb(i);
            }
        }
    }
    //assert(!Le.empty());
    //assert(!Bi.empty());
    Solve(Le, L, L + Le.size() - 1);
    Solve(Bi, Le.size(), R);
}

void allValues(int n, int w, int *P) {
    if (w == 2 * n) {
        return ;
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            int ln = j - i + 1;
            vector<int> A, B;
            for(int k = n; k >= 1; k--){
                if(i <= k && k <= j) A.pb(k);
                else B.pb(k);
            }
            int val = -1;
            for(int x = 1; x * ln <= n; x++){
                int mx = -1;
                vector<int> Mx;
                for(int cn = 0; cn <= ln; cn ++){
                    if(cn * (x + 1) > n) continue;
                    int res = 0;
                    for(int i2 = 0; i2 < cn; i2 ++) res += A[i2];
                    int cn2 = min(n - (cn * (x + 1)), (int) B.size());
                    for(int i2 = 0; i2 < cn2; i2 ++) res += B[i2];
                    if(res > mx){
                        mx = res;
                        Mx.clear();
                    }
                    if(res == mx) Mx.pb(cn);
                }
                if(!Mx.empty() && (Mx[0] != 0) && (Mx.back() != ln)){
                    val = x;
                }
            }
            dp[i][j] = val;
        }
    }
    vector<int> I(n);
    iota(I.begin(), I.end(), 0); 
    Solve(I, 1, n);

    for(int i = 0; i < n; i++)
        P[i] = ans[i];
}

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