Submission #807236

#	Time	Username	Problem	Language	Result	Execution time	Memory
807236		hugo_pm	Koala Game (APIO17_koala)	C++17	74 / 100	53 ms	456 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;
}

bool comp(int N, int W, int i, int j) { // P[i] < P[j]
    if (i == j) return false;
    if (W == 2*N) {
        reset();
        moi[i] = moi[j] = N;
        play();
        return won[j];
    } else {
        assert(W == N);
        reset();
        int lo = 1, hi = min(9, W/2);
        while (lo <= hi) {
            int mid = (lo+hi)/2;
            reset();
            moi[i] = moi[j] = mid;
            play();
            if (won[i] < won[j]) return true;
            if (won[i] > won[j]) return false;
            if (!won[i]) hi = mid-1;
            else lo = mid+1;
        }
    }
}
int greaterValue(int N, int W) {
    return (comp(N, W, 0, 1) ? 1 : 0);
}

void allValues(int N, int W, int *P) {
    auto Merge = [&] (auto merge, vector<int> A) {
        int sz = A.size();
        if (sz <= 1) return A;
        vector<int> L(A.begin(), A.begin() + sz/2), R(A.begin() + sz/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(N, W, 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;
    }
}

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 | }
      | ^
koala.cpp: In function 'bool comp(int, int, int, int)':
koala.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

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