Submission #1195618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195618		abczz	코알라 (APIO17_koala)	C++20	100 / 100	36 ms	468 KiB

koala

#include "koala.h"
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

int B[100], R[100], F[100];
bool X[100];
int minValue(int N, int W) {
    for (int i=0; i<N; ++i) B[i] = 0;
    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) {
    for (int i=0; i<N; ++i) X[i] = 1;
    ll m = N, s = 0;
    while (m != 1) {
        for (int i=0; i<N; ++i) {
            if (X[i]) B[i] = W/m;
            else B[i] = 0;
        }
        playRound(B, R);
        s = 0;
        for (int i=0; i<N; ++i) {
            if (R[i] > B[i] && X[i]) X[i] = 1, ++s;
            else X[i] = 0;
        }
        m = s;
    }
    for (int i=0; i<N; ++i) {
        if (X[i]) return i;
    }
}

int greaterValue(int N, int W) {
    vector <ll> Z = {1, 3, 5, 7, 10};
    for (int i=0; i<N; ++i) {
        B[i] = 0;
    }
    ll l = 0, r = 4, mid;
    while (l < r) {
        mid = (l+r)/2;
        B[0] = B[1] = Z[mid];
        playRound(B, R);
        if (R[0] > B[0] && R[1] > B[1]) l = mid+1;
        else if (R[0] <= B[0] && R[1] <= B[1]) r = mid-1;
        else if (R[0] > B[0]) return 0;
        else return 1;
    }
    B[0] = B[1] = Z[l];
    playRound(B, R);
    if (R[0] > B[0]) return 0;
    else return 1;
}

void split(ll l, ll r, vector<ll> V, ll W) {
    if (l == r) {
        F[V[0]] = l;
        return;
    }
    for (ll k=1; k<=W/(r-l+1); ++k) {
        vector <ll> C, D;
        for (int j=1; j<l; ++j) C.push_back(j);
        for (int j=r+1; j<=100; ++j) C.push_back(j);
        for (int j=l; j<=r; ++j) D.push_back(j);
        ll s = W;
        while (s) {
            if (s >= (k+1) && !D.empty()) {
                ll z = 0;
                for (int j=0; j<min((ll)C.size(), k+1); ++j) z += C[(ll)C.size()-1-j];
                if (D.back() > z) {
                    D.pop_back();
                    s -= (k+1);
                }
                else {
                    C.pop_back();
                    --s;
                }
            }
            else break;
        }
        if (!D.empty() && D.size() != r-l+1) {
            for (int j=0; j<100; ++j) B[j] = 0;
            for (auto u : V) {
                B[u] = k;
            }
            playRound(B, R);
            C.clear();
            D.clear();
            for (auto u : V) {
                if (R[u] > B[u]) D.push_back(u);
                else C.push_back(u);
            }
            split(l, l+C.size()-1, C, W);
            split(l+C.size(), r, D, W);
            return;
        }
    }
}

void allValues(int N, int W, int *P) {
    vector <ll> V;
    for (int i=0; i<N; ++i) V.push_back(i);
    split(1, N, V, W);
    for (int i=0; i<N; ++i) P[i] = F[i];
}

Compilation message (stderr)

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

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