Submission #1179856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179856		NValchanov	Koala Game (APIO17_koala)	C++20	47 / 100	29 ms	460 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>

using namespace std;

int minValue(int n, int w) 
{
    int b[n];
    int r[n];
    
    for(int i = 1; i < n; i++)
    {
        b[i] = 0;
    }
    b[0] = 1;

    playRound(b, r);

    if(r[0] <= 1)
        return 0;

    for(int i = 1; i < n; i++)
    {
        if(r[i] == 0)
            return i;
    }

    return 0;
}

int maxValue(int n, int w) 
{
    int b[n];
    int r[n];
    vector < int > maxset;

    for(int i = 0; i < n; i++)
    {
        maxset.push_back(i);
    }

    while(maxset.size() > 1)
    {
        int sz = maxset.size();
        int by = w / sz;

        for(int i = 0; i < n; i++)
        {
            b[i] = 0;
        }
        for(int idx : maxset)
        {
            b[idx] = by;
        }

        playRound(b, r);

        maxset.clear();

        for(int i = 0; i < n; i++)
        {
            if(r[i] > by)
                maxset.push_back(i);
        }
    }

    return maxset[0];

    return 0;
}

int n;
int w;

bool cmp(int idx1, int idx2, int *b, int *r)
{
    int left = 0;
    int right = 15;
    int mid;

    for(int i = 0; i < n; i++)
    {
        b[i] = 0;
    }

    while(right - left > 1)
    {
        mid = left + (right - left) / 2;

        b[idx1] = b[idx2] = mid;

        playRound(b, r);

        b[idx1] = b[idx2] = 0;

        if(r[idx1] <= mid && r[idx2] <= mid)
            right = mid;
        else if(r[idx1] > mid && r[idx2] > mid)
            left = mid;
        else
        {
            b[idx1] = b[idx2] = 0;
            return r[idx1] < r[idx2];
        }
    }

    b[idx1] = b[idx2] = left;
    playRound(b, r);

    b[idx1] = b[idx2] = 0;
    return r[idx1] < r[idx2];
}

int greaterValue(int N, int W) 
{
    n = N;
    w = W;
    int b[n];
    int r[n];
    for(int i = 0; i < n; i++)
    {
        b[i] = 0;
    }
    
    return cmp(0, 1, b, r);
}

vector < int > a;
vector < int > tmp;

void merge_sort(int left, int right, int *b, int *r, int by)
{
    if(left == right)
        return;

    int mid = left + (right - left) / 2;

    merge_sort(left, mid, b, r, by);
    merge_sort(mid + 1, right, b, r, by);

    int ptrl = left;
    int ptrr = mid + 1;
    int ptr = left;

    while(ptrl <= mid && ptrr <= right)
    {
        for(int i = 0; i < n; i++)
        {
            b[i] = 0;
        }

        b[a[ptrl]] = b[a[ptrr]] = by;
        playRound(b, r);

        if(r[a[ptrr]] > by)
        {
            tmp[ptr++] = a[ptrl++]; 
        }
        else
        {
            tmp[ptr++] = a[ptrr++];
        }
    }

    while(ptrl <= mid)
        tmp[ptr++] = a[ptrl++];
    
    while(ptrr <= right)
        tmp[ptr++] = a[ptrr++];

    for(int i = left; i <= right; i++)
    {
        a[i] = tmp[i];
    }
}

void allValues(int N, int W, int *p) 
{
    n = N;
    w = W;
    int b[n];
    int r[n];

    for(int i = 0; i < n; i++)
    {
        b[i] = 0;
    }

    a.resize(n);
    tmp.resize(n);

    for(int i = 0; i < n; i++)
    {
        a[i] = i;
    }

    merge_sort(0, n - 1, b, r, w == 2 * n ? n : n / 2);

    for(int i = 0; i < n; i++)
    {
        p[a[i]] = i + 1;
    }
}

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