Submission #267038

#	Time	Username	Problem	Language	Result	Execution time	Memory
267038		amoo_safar	Koala Game (APIO17_koala)	C++17	100 / 100	135 ms	532 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

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], np, rq;

int minValue(int n, int w) {
    assert(n == w);

    memset(inp, 0, sizeof inp);
    memset(out, 0, sizeof out);
    inp[0] = 1;
    playRound(inp, out);
    for(int i = 0; i < n; i++) if(inp[i] >= out[i]) return i;
    return 0;
}


int maxValue(int n, int w) {
    assert(n == 100);
    int Ask[4] = {1, 2, 4, 11};
    int req[4] = {50, 25, 9, 1};
    vector<int> I(n);
    iota(I.begin(), I.end(), 0);
    for(int it = 0; it < 4; it ++){
        memset(inp, 0, sizeof inp);
        memset(out, 0, sizeof out);
        for(auto x : I) inp[x] = Ask[it];
        playRound(inp, out);
        
        I.clear();
        for(int i = 0; i < 100; i++){
            if((out[i] > inp[i]) && (inp[i] > 0)) I.pb(i);
        }
        assert(((int) I.size() == req[it]));
    }
    assert(((int)I.size() == 1));  
    return I[0];
}


int greaterValue(int n, int w) {
    assert(n == 100);
    //int req[4] = {50, 25, 9, 1};
    vector<int> I(2);
    iota(I.begin(), I.end(), 0);
    int L = -1, R = 4, it;
    while(L + 1 < R){
        it = (L + R) >> 1;
        memset(inp, 0, sizeof inp);
        memset(out, 0, sizeof out);
        for(auto x : I) inp[x] = 1 << it;
        playRound(inp, out);
        
        I.clear();
        for(int i = 0; i < 100; i++){
            if((out[i] > inp[i]) && (inp[i] > 0)) I.pb(i);
        }
        if(I.size() == 1) break;
        if(I.empty()){
            I.pb(0);
            I.pb(1);
            R = it;
        } else {
            L = it;
        }
        //assert(((int) I.size() == req[it]));
    }
    assert(((int)I.size() == 1));  
    return I[0];
}


bool CMP(int i, int j){
    memset(inp, 0, sizeof inp);
    memset(out, 0, sizeof out);
    inp[i] = np;
    inp[j] = np;
    playRound(inp, out);
    rq --;
    if(rq == 0) assert(false);
    return out[i] <= inp[i];
}


void Solve(vector<int> pos, int L, int R){
    //int n = np;
    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;
    memset(out, 0, sizeof out);
    playRound(inp, out);
    vector<int> Le, Bi;
    for(int i = 0; i < np; i++){
        if(inp[i] > 0){
            if(inp[i] < out[i]){
                Bi.pb(i);
            } else {
                Le.pb(i);
            }
        }
    }
    /*
    if(Le.empty()){
        cerr << "! " << L << " " << R << " -> " << pos.size() << '\n';
        //for(int i = 0; i < 100; i++) cerr << inp[i] << ' ' << out[i] << '\n';
        cerr << '\n';
    }
    */
    assert(!Le.empty());
    assert(!Bi.empty());
    Solve(Le, L, L + Le.size() - 1);
    Solve(Bi, L + Le.size(), R);
}

void allValues(int n, int w, int *P) {
    np = n;
    if (w == 2 * n) {
        rq = 700;
        vector<int> I;
        I.pb(0);
        for(int i = 1; i < n; i++){
            int L = -1, R = I.size();
            while(L + 1 < R){
                int mid = (L + R) >> 1;
                if(CMP(I[mid], i)) L = mid;
                else R = mid;
            }
            I.insert(I.begin() + (L + 1), i);
        }
        for(int i = 0; i < n; i++)
            P[I[i]] = i + 1;
        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];
}
/*
4 1
6 12 5 3 2 1 6 4

*/

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