Submission #807215

#	Time	Username	Problem	Language	Result	Execution time	Memory
807215		hugo_pm	Koala Game (APIO17_koala)	C++17	47 / 100	48 ms	356 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100;
int moi[MAX_N], adverse[MAX_N], won[MAX_N];

void play() {
    playRound(moi, adverse);
    for (int i = 0; i < MAX_N; ++i) {
        won[i] = (adverse[i] > moi[i]);
    }
}

void reset() {
    memset(moi, 0, sizeof(moi));
    memset(adverse, 0, sizeof(adverse));
    memset(won, 0, sizeof(won));
}
int minValue(int N, int W) {
    reset();
    moi[0] = 1;
    play();
    for (int i = 0; i < N; ++i) {
        if (!won[i]) {
            return i;
        }
    }
}

int maxValue(int N, int W) {
    reset();
    vector<int> isCand(N, 1);
    int cnt = N;
    while (cnt > 1) {
        reset();
        int perPos = N/cnt;
        for (int i = 0; i < N; ++i) {
            if (isCand[i]) {
                moi[i] = perPos;
            }
        }
        play();
        cnt = 0;
        for (int i = 0; i < N; ++i) {
            isCand[i] &= won[i];
            cnt += isCand[i];
        }
    }
    int argMax = 0;
    while (!isCand[argMax]) ++argMax;
    return argMax;
}

int greaterValue(int N, int W) {
    reset();
    int lo = 1, hi = 9;
    while (lo <= hi) {
        int mid = (lo+hi)/2;
        reset();
        moi[0] = moi[1] = mid;
        play();
        if (won[0] > won[1]) return 0;
        if (won[0] < won[1]) return 1;
        if (!won[0]) hi = mid-1;
        else lo = mid+1;
    }
    return -1;
}

void s4(int N, int W, int *P) {
    auto comp = [&] (int i, int j) -> bool { // P[i] < P[j] ?
        if (i == j) return false;
        reset();
        moi[i] = moi[j] = N;
        play();
        return won[j];
    };
    auto Merge = [&] (auto merge, vector<int> A) {
        int N = A.size();
        if (N <= 1) return A;
        vector<int> L(A.begin(), A.begin() + N/2), R(A.begin() + N/2, A.end());
        L = merge(merge, L);
        R = merge(merge, R);
        A.clear();
        reverse(L.begin(), L.end());
        reverse(R.begin(), R.end());
        while (!L.empty() || !R.empty()) {
            auto &take = (R.empty() || (!L.empty() && comp(L.back(), R.back()))) ? L : R;
            A.push_back(take.back());
            take.pop_back();
        }
        return A;
    };
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    order = Merge(Merge, order);
    for (int i = 0; i < N; ++i) {
        P[order[i]] = i+1;
    }
}
void allValues(int N, int W, int *P) {
    reset();
    if (W == 2*N) {
        s4(N, W, P);
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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