Submission #1181050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181050		n3rm1n	Koala Game (APIO17_koala)	C++20	90 / 100	36 ms	472 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 10;
int minValue(int N, int W)
{
    int n = N;
    int b[N+1], r[N+1];
    for (int i = 0; i < N; ++ i)
    {
        b[i] = 0;
        r[i] = 0;
    }

    b[0] = 1;
    playRound(b, r);
    for (int i = 0; i < n; ++ i)
        if(r[i] == 0)return i;

    return 0;
}

int maxValue(int N, int W)
{
    int n = N;
    int b[n+1], r[n+1];
    vector < int > pot;
    for (int i = 0; i < n; ++ i)
        pot.pb(i);
    while(pot.size() > 1)
    {
        int dajba = n/pot.size();
        for (int i = 0; i < n; ++ i)
        {
            b[i] = 0;
            r[i] = 0;
        }
        for (int i = 0; i < pot.size(); ++ i)
        {
            int x = pot[i];
            b[x] = dajba;
        }
        playRound(b, r);
        vector < int > newpot;
        for (int i = 0; i < pot.size(); ++ i)
        {
            int taken = pot[i];
            if(r[taken])newpot.pb(taken);
        }
        pot = newpot;

    }
    return pot[0];
}

int greaterValue(int N, int W)
{
    int n = N;
    int b[N], r[N];
    int l = 0, ri = 9, mid;
    while(l <= ri)
    {
        mid = (l + ri)/2;
        for (int i = 0; i < n; ++ i)
        {
            b[i] = 0;
            r[i] = 0;
        }
        b[0] = b[1] = mid;
        playRound(b, r);
        if(r[0] == r[1])
        {
            if(r[0])l = mid + 1;
            else ri = mid - 1;
        }
        else if(r[0])return 0;
        else return 1;

    }
    return 0;
}
int n, w;
int b[maxn], rk[maxn];
vector < int > solve(vector < int > g, int l, int r)
{

    for (int i = 0; i < g.size(); ++ i)
    {
        int x = g[i];

    }

    vector < int > ans;
    if(r < l)return ans;
    if(l == r)return g;

    int sz = r - l + 1;
    int dajba = min((int)(sqrt(2*l)), w / sz);
    for (int i = 0; i < n; ++ i)
    {
        b[i] = 0;
        rk[i] = 0;
    }
    for (int i = 0; i < g.size(); ++ i)
    {
        b[g[i]] = dajba;
    }
    playRound(b, rk);
    vector < int > bigger, smaller;
    for (int i = 0; i < n; ++ i)
    {
        if(b[i] && rk[i])bigger.pb(i);
        else if(b[i])smaller.pb(i);
    }

    int cnt1 = smaller.size();
    int cnt2 = bigger.size();
    smaller = solve(smaller, l, l + cnt1 - 1);
    bigger = solve(bigger, l + cnt1, r);
    for (int i = 0; i < smaller.size(); ++ i)
        ans.pb(smaller[i]);
    for (int i = 0; i < bigger.size(); ++ i)
        ans.pb(bigger[i]);
    return ans;
}
void allValues(int N, int W, int *P)
{

    n = N;
    w = W;
    if (W == 2*N)
    {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
    else
    {

        vector < int > g;
        for (int i = 0; i < N; ++ i)
            g.pb(i);
        g = solve(g, 1, N);
        for (int i = 0; i < g.size(); ++ i)
        {

            int pos = g[i];
            P[pos] = i + 1;
        }

    }
}

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