Submission #717135

#	Time	Username	Problem	Language	Result	Execution time	Memory
717135		tht2005	Koala Game (APIO17_koala)	C++17	100 / 100	64 ms	348 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 102;

int B[N], R[N];

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

int maxValue(int N, int W) {
    vector<int> S(N);
    iota(S.begin(), S.end(), 0);
    while((int)S.size() > 1) {
        memset(B, 0, N * sizeof *B);
        for(int i : S) {
            B[i] = N / S.size();
        }
        playRound(B, R);
        vector<int> T;
        for(int i : S) {
            if(R[i] > B[i]) {
                T.push_back(i);
            }
        }
        S.swap(T);
    }
    return S[0];
}

int greaterValue(int N, int W) {
    memset(B, 0, N * sizeof *B);
    int l = 1, r = 9;
    while(l <= r) {
        int mid = (l + r) >> 1;
        B[0] = B[1] = mid;
        playRound(B, R);
        bool check = (R[0] > B[0]), check1 = (R[1] > B[1]);
        if(check != check1) {
            return check ? 0 : 1;
        }
        if(check) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
}

bool compare(int i, int j) {
    memset(B, 0, sizeof(B));
    B[i] = B[j] = 100;
    playRound(B, R);
  	return (R[j] > B[j]);
}

void solve(int l, int r, vector<int>& A) {
    if(l == r) {
        return;
    }
    int m = (l + r) >> 1;
    solve(l, m, A);
    solve(m + 1, r, A);
    vector<int> B(r + 1 - l);
    for(int i = l, j = l, k = m + 1; i <= r; ++i) {
        if(k > r || (j <= m && compare(A[j], A[k]))) {
            B[i - l] = A[j++];
        }
        else {
            B[i - l] = A[k++];
        }
    }
    for(int i = l; i <= r; ++i) {
        A[i] = B[i - l];
    }
}

void split(const vector<int>& pos, int l, int r, int *P) {
    if(l == r) {
        P[pos[0]] = l;
    }
    else {
        int val = min((int)sqrt(l + l), 100 / (r - l + 1));
        memset(B, 0, sizeof(B));
        for(int i : pos) {
            B[i] = val;
        }
        playRound(B, R);
        vector<int> small, big;
        for(int i : pos) {
            if(R[i] > B[i]) {
                big.push_back(i);
            }
            else {
                small.push_back(i);
            }
        }
        split(small, l, l - 1 + small.size(), P);
        split(big, l + small.size(), r, P);
    }
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector<int> A(N);
        iota(A.begin(), A.end(), 0);
        solve(0, N - 1, A);
        for(int i = 0; i < N; ++i) {
            P[A[i]] = i + 1;
        }
    }
    else {
        vector<int> pos(N);
        iota(pos.begin(), pos.end(), 0);
        split(pos, 1, N, P);
    }
}

Compilation message (stderr)

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

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