Submission #157337

#	Time	Username	Problem	Language	Result	Execution time	Memory
157337		dolphingarlic	Koala Game (APIO17_koala)	C++14	100 / 100	69 ms	540 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#define pb push_back
#define bg begin
using namespace std;

int B[100], R[100];

bool cmp(int a, int b, int N, int W) {
    fill(B, B + N, 0);
    B[a] = B[b] = W;
    playRound(B, R);
    return (R[b] > W);
}
vector<int> mgs(vector<int> v, int N, int W) {
    if (v.size() == 1) return v;
 
    vector<int> a, b;
    a.insert(a.bg(), v.bg(), v.bg() + (v.size() + 1) / 2);
    b.insert(b.bg(), v.bg() + (v.size() + 1) / 2, v.end());
    a = mgs(a, N, W), b = mgs(b, N, W);
 
    vector<int> st;
    int aptr = 0, bptr = 0;
    while (aptr < a.size() && bptr < b.size()) {
        if (cmp(a[aptr], b[bptr], N, W)) st.pb(a[aptr++]);
        else st.pb(b[bptr++]);
    }
    st.insert(st.end(), a.bg() + aptr, a.end());
    st.insert(st.end(), b.bg() + bptr, b.end());
 
    return st;
}

void sp(vector<int> v, int N, int W, int* P, int l = 1, int r = 100) {
    if (l == r) P[v[0]] = l;
    else {
        int x = min((int)sqrt(2 * l), W / (r - l + 1));

        fill(B, B + N, 0);
        for (int i : v) B[i] = x;

        playRound(B, R);
        vector<int> ll, gg;
        for (int i : v) if (R[i] > x) gg.pb(i);
        else ll.pb(i);

        sp(ll, N, W, P, l, l + ll.size() - 1);
        sp(gg, N, W, P, r - gg.size() + 1, r);
    }
}

int minValue(int N, int W) {
    fill(B, B + N, 0);
    fill(R, R + N, 0);
    B[0] = 1;
    playRound(B, R);
    if (R[0] < 2) return 0;
    else for (int i = 1; i < N; i++) if (!R[i]) return i;
    return -1;
}

int maxValue(int N, int W) {
    vector<int> v;
    for (int i = 0; i < N; i++) v.pb(i);
    while (v.size() != 1) {
        int k = W / v.size();
        fill(B, B + N, 0);
        for (int i : v) B[i] = k;
        playRound(B, R);
        v.clear();
        for (int i = 0; i < N; i++) if (R[i] > k) v.pb(i);
    }
    return v[0];
}

int greaterValue(int N, int W) {
    int l = 1, r = 9;
    while (l != r) {
        int mid = (l + r) / 2;
        B[0] = B[1] = mid;
        playRound(B, R);

        if (R[0] > mid && R[1] > mid) l = mid + 1;
        else if (R[0] <= mid && R[1] <= mid) r = mid - 1;
        else return (R[0] < R[1]);
    }
    B[0] = B[1] = l;
    playRound(B, R);
    return (R[0] < R[1]);
}

void allValues(int N, int W, int *P) {
    if (W == 2 * N) {
        vector<int> v;
        for (int i = 0; i < N; i++) v.pb(i);
        vector<int> st = mgs(v, N, W / 2);
        for (int i = 0; i < N; i++) P[st[i]] = i + 1;
    } else {
        vector<int> v;
        for (int i = 0; i < N; i++) v.pb(i);
        sp(v, N, W, P);
    }
}

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> mgs(std::vector<int>, int, int)':
koala.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (aptr < a.size() && bptr < b.size()) {
            ~~~~~^~~~~~~~~~
koala.cpp:25:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (aptr < a.size() && bptr < b.size()) {
                               ~~~~~^~~~~~~~~~

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