Submission #1173481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173481		anmattroi	Koala Game (APIO17_koala)	C++17	100 / 100	36 ms	460 KiB

koala

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

using namespace std;

int minValue(int N, int W) {
    vector<int> B(N, 0), R(N, 0);

    B[0] = 1;

    playRound(B.data(), R.data());
    if (R[0] < 2) return 0;
    for (int i = 1; i < N; i++)
        if (!R[i]) return i;
    return 0;
}

int maxValue(int N, int W) {
    vector<int> candidates, B(N, 0), R(N, 0);

    for (int i = 0; i < N; i++) candidates.emplace_back(i);
    while (candidates.size() > 1) {
        int k = W / candidates.size();
        fill(B.begin(), B.end(), 0);
        for (int i : candidates) B[i] = k;
        playRound(B.data(), R.data());
        candidates.clear();
        for (int i = 0; i < N; i++)
            if (R[i] > k) candidates.emplace_back(i);
    }
    return candidates[0];
}

int greaterValue(int N, int W) {
    int lo = 1, hi = 9;
    vector<int> B(N, 0), R(N, 0);
    while (lo != hi) {
        int mid = (lo + hi) >> 1;
        B[0] = B[1] = mid;
        playRound(B.data(), R.data());
        if (R[0] > mid && R[1] > mid) lo = mid+1;
        else if (R[0] <= mid && R[1] <= mid) hi = mid-1;
        else return (R[0] < R[1]);
    }
    B[0] = B[1] = lo;
    playRound(B.data(), R.data());
    return (R[0] < R[1]);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector<int> B(N, 0), R(N, 0);

        function<vector<int>(int, int)> merge_sort = [&](int lo, int hi) {
            if (lo == hi) return vector<int>(1, lo);
            int mid = (lo + hi) >> 1;
            vector<int> Lef = merge_sort(lo, mid), Rig = merge_sort(mid+1, hi);
            vector<int> ans;
            int l = 0, r = 0;
            while (l < Lef.size() || r < Rig.size()) {
                if (l == Lef.size()) {ans.emplace_back(Rig[r]); ++r; continue;}
                if (r == Rig.size()) {ans.emplace_back(Lef[l]); ++l; continue;}
                int u = Lef[l], v = Rig[r];
                B[u] = B[v] = W/2;
                playRound(B.data(), R.data());
                B[u] = B[v] = 0;

                if (R[u] < R[v]) {
                    ans.emplace_back(Lef[l]); ++l;
                } else {
                    ans.emplace_back(Rig[r]); ++r;
                }
            }
            return ans;
        };
        vector<int> Lis = merge_sort(0, N-1);
        for (int i = 0; i < N; i++) P[Lis[i]] = i+1;
    } else {
        vector<int> B(N, 0), R(N, 0);

        function<void(vector<int>, int, int)> split = [&](vector<int> v, int lo, int hi) {
            if (lo == hi) {
                P[v[0]] = lo;
                return;
            }
            int x = min(int(sqrt(2*lo)), W / (hi-lo+1));
            fill(B.begin(), B.end(), 0);
            for (int i : v) B[i] = x;
            playRound(B.data(), R.data());
            vector<int> lesser, morer;
            for (int i : v)
                if (R[i] > x) morer.emplace_back(i);
                else lesser.emplace_back(i);
            split(lesser, lo, lo+lesser.size()-1);
            split(morer, lo+lesser.size(), hi);
        };
        vector<int> v(N, 0);
        for (int i = 0; i < N; i++) v[i] = i;
        split(v, 1, N);
    }
}

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