Submission #1216154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216154		jasonic	Koala Game (APIO17_koala)	C++20	47 / 100	49 ms	1016 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100;
int toSend[MXN];
int response[MXN];

int minValue(int n, int w) {

    toSend[0] = 1;

    playRound(toSend, response);

    for(int i = 1; i < MXN; i++) {
        if(response[i] == 0) return i;
    }
    
    return 0;
}

int maxValue(int n, int w) {
    vector<int> candidates;
    for(int i = 0; i < MXN; i++) candidates.push_back(i);
    
    while(candidates.size() != 1) {
        int cnt = w / candidates.size();
        fill(toSend, toSend + MXN, 0);
        for(auto i : candidates) toSend[i] = cnt;
        playRound(toSend, response);
        candidates.clear();
        for(int i = 0; i < MXN; i++) if(response[i] > cnt) candidates.push_back(i);
    }

    return candidates[0];
}

int greaterValue(int n, int w) {
    int l = 0;
    int r = 10;

    while (l + 1 < r) {
        int m = (l+r)/2;
        toSend[0] = m;
        toSend[1] = m;
        playRound(toSend, response);

        if(response[0] <= m && response[1] <= m) {
            r = m;
        } else if(response[0] > m && response[1] > m) {
            l = m;
        } else {
            return response[0] < response[1];
        }
    }

    toSend[0] = r;
    toSend[1] = r;
    playRound(toSend, response);

    return response[0] < response[1];
}

int S[100];

bool compare1(int a, int b) {
    fill(toSend, toSend + MXN, 0);
    toSend[a] = 100;
    toSend[b] = 100;

    playRound(toSend, response);
    return response[a] < response[b];
}

void conquer1(int l_l, int l_r, int r_l, int r_r) {
    queue<int> a, b, c;
    for(int i = l_l; i <= l_r; i++) a.push(S[i]);
    for(int i = r_l; i <= r_r; i++) b.push(S[i]);

    while(!a.empty() && !b.empty()) {
        if(compare1(a.front(), b.front())) {
            c.push(a.front());
            a.pop();
        } else {
            c.push(b.front());
            b.pop();
        }
    }

    while(!a.empty()) {
        c.push(a.front());
        a.pop();
    }

    while(!b.empty()) {
        c.push(b.front());
        b.pop();
    }

    for(int i = l_l; i <= r_r; i++) {
        S[i] = c.front();
        c.pop();
    }
}

void divide1(int l, int r) {
    if(l != r) {
        int m = l + (r-l)/2;
        divide1(l, m);
        divide1(m+1, r);
        conquer1(l, m, m+1, r);
    }
}

int triangle(int k) {
    return (k * (k+1) / 2);
}

int binSearch(int v) {
    int l, r; 
    l = -1, r = 17;
    while(l + 1 < r) {
        int m = (l+r)/2;
        if(triangle(m) < v) l = m;
        else r = m;
    }
    return r;
}

void solve(int l, int r, vector<int> idxs) {
    if(l == r) {
        S[idxs[0]] = l;
        return;
    }

    int m = min(100/(r-l+1), binSearch(r));

    for(int i = 0; i < 100; i++) toSend[i] = 0;
    for(int idx : idxs) toSend[idx] = m;

    playRound(toSend, response);
    vector<int> leftArr, rightArr;

    int lr = l - 1;

    for(int idx : idxs) {
        if(response[idx] <= m) {
            leftArr.push_back(idx);
            lr++;
        }
        else rightArr.push_back(idx);
    }

    solve(l, lr, leftArr);
    solve(lr+1, r, rightArr);
}

void allValues(int n, int w, int *p) {
    if (w == 2*n) {
        for(int i = 0; i < n; i++) S[i] = i;
        divide1(0, n-1); // S is now sorted in order of the indices with increasing value
        
        for(int i = 0; i < n; i++) p[S[i]] = i+1;
    } else {
        vector<int> a; for(int i = 0; i < 100; i++) a.push_back(i);
        solve(1, 100, a);
        for(int i = 0; i < n; i++) p[i] = S[i];
    }
}

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