제출 #385192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385192		phathnv	코알라 (APIO17_koala)	C++11	100 / 100	91 ms	492 KiB

koala

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

using namespace std;

int minValue(int N, int W) {
    int b[N], r[N];
    memset(b, 0, sizeof(b));
    b[0] = 1;
    playRound(b, r);
    for(int i = 0; i < N; i++)
        if (r[i] == 0)
            return i;
    return 0;
}

int maxValue(int N, int W) {
    vector<int> candidates;
    for(int i = 0; i < N; i++)
        candidates.push_back(i);
    while (candidates.size() > 1){
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        int c = min(12, W / (int) candidates.size());
        for(int ind : candidates)
            b[ind] = c;
        playRound(b, r);
        vector<int> nxt;
        for(int i = 0; i < N; i++)
            if (b[i] == c && r[i] > c)
                nxt.push_back(i);
        candidates = nxt;
    }
    return candidates.front();
}

int greaterValue(int N, int W) {
    int val[6] = {1, 2, 4, 6, 7, 8};
    int lo = 0, hi = 5;
    while (lo <= hi){
        int mid = (lo + hi) >> 1;
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        b[0] = b[1] = val[mid];
        playRound(b, r);
        if (r[0] > b[0] && r[1] <= b[1])
            return 0;
        else if (r[0] <= b[0] && r[1] > b[1])
            return 1;
        else if (r[0] <= b[0] && r[1] <= b[1])
            hi = mid - 1;
        else
            lo = mid + 1;
    }

    return 0;
}

int ptr;
int key[2][99] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 4, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 5, 1, 2, 2, 3, 5, 3, 4, 5, 2, 5, 2, 3, 4, 5, 4, 4, 6, 1, 2, 3, 5, 6, 3, 4, 6, 5, 6, 1, 4, 5, 6, 1, 7, 1, 2, 2, 2, 3, 4, 5, 7, 3, 4, 7, 5, 6, 7, 2, 5, 6, 7, 2, 2, 3, 4, 5, 6, 8, 3, 4, 6, 8, 5, 8, 6, 8},
    {2, 3, 4, 15, 17, 21, 26, 35, 52, 4, 5, 26, 35, 53, 5, 6, 35, 53, 7, 53, 8, 53, 9, 54, 10, 11, 12, 14, 16, 18, 22, 27, 36, 54, 2, 18, 22, 28, 37, 55, 2, 55, 2, 3, 8, 9, 10, 10, 11, 13, 14, 16, 19, 22, 28, 37, 56, 3, 28, 37, 56, 3, 4, 14, 16, 19, 23, 28, 38, 56, 4, 5, 23, 28, 38, 56, 5, 6, 28, 38, 57, 7, 38, 57, 8, 57, 9, 57, 10, 11, 12, 13, 15, 17, 19, 23, 29, 38, 57}
};
void solve(int N, int W, int l, int r, vector<int> candidates, int *P){
    assert((int) candidates.size() == r - l + 1);
    if (candidates.size() == 1){
        P[candidates.front()] = l;
        return;
    }

    vector<int> toLeft, toRight;
    int k = key[W / N - 1][ptr++];
    while (toLeft.empty() || toRight.empty()){
        int b[N], r[N];
        memset(b, 0, sizeof(b));
        for(int x : candidates)
            b[x] = k;
        playRound(b, r);
        toLeft.clear();
        toRight.clear();
        for(int x : candidates)
            if (r[x] <= b[x])
                toLeft.push_back(x);
            else
                toRight.push_back(x);
    }
    solve(N, W, l, l + toLeft.size() - 1, toLeft, P);
    solve(N, W, l + toLeft.size(), r, toRight, P);
}

void allValues(int N, int W, int *P) {
    ptr = 0;
    vector<int> a;
    for(int i = 0; i < N; i++)
        a.push_back(i);
    solve(N, W, 1, N, a, P);
}

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