Submission #1178563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178563		amine_aroua	Koala Game (APIO17_koala)	C++20	59 / 100	43 ms	460 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int sub = 0;
int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int B[N] , R[N];
    B[0] = 1;
    for(int i = 1 ; i < N ;i++)
    {
        B[i] = 0;
        R[i] = 0;
    }
    playRound(B , R);
    for(int i = 0 ;i < N ; i++)
    {
        if(R[i] <= B[i])
        {
            return i;
        }
    }
    return 0;
}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int B[N] , R[N];
    // cout<<"HELLO\n";
    for(int i = 0 ; i < N ;i++)
    {
        B[i] = 1;
        R[i] = 0;
    }
    int nb1 = N;
    int ret = 0;
    vector<bool> bad(N);
    while(nb1 > 1)
    {
        // cout<<"B : ";
        // for(int i = 0 ; i < N ; i++)
        // {
        //     cout<<B[i]<<" ";
        // }
        // cout<<'\n';
        playRound(B , R);
        // cout<<"R : ";
        // for(int i = 0 ; i < N ; i++)
        // {
        //     cout<<R[i]<< " ";
        // }
        // cout<<'\n';
        nb1 = 0;
        for(int i = 0 ; i < N ; i++)
        {
            if(bad[i])
                continue;
            if(R[i] <= B[i])
            {
                bad[i] = 1;
                B[i] = 0;
            }
            else
            {
                B[i]++;
                nb1++;
                ret = i;
            }
        }

    }
    return ret;
}

int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int lo = 0 , hi = 9;
    int a = 0 , b = 1;
    while(lo + 1 < hi)
    {
        int md = (lo + hi) / 2ll;
        int B[N] , R[N];
        for(int i = 0 ; i < N ; i++)
        {
            B[i] = 0;
            R[i] = 0;
        }
        B[a] = md;
        B[b] = md;
        playRound(B , R);
        int aa = (R[a] > B[a]);
        int bb = (R[b] > B[b]);
        if(aa == 0 && bb == 0)
        {
            hi = md;
        }
        else if(aa == 1 && bb == 1)
        {
            lo = md;
        }
        else
            return bb;
    }
    return 1;
}

bool cmp(const int &a, const int &b ) {
    int N = 100;
    if(a == b)
        return 0;
    if(sub == 0)
    {
        int B[N] , R[N];
        for(int i = 0 ; i < N ; i++)
        {
            B[i] = 0 , R[i] = 0;
        }
        B[a] = N;
        B[b] = N;
        playRound(B , R);
        if(R[b] > B[b])
            return 1;
        return  0;
    }
    else
    {
        int lo = 0 , hi = 9;
        while(lo + 1 < hi)
        {
            int md = (lo + hi) / 2ll;
            int B[N] , R[N];
            for(int i = 0 ; i < N ; i++)
            {
                B[i] = 0;
                R[i] = 0;
            }
            B[a] = md;
            B[b] = md;
            playRound(B , R);
            int aa = (R[a] > B[a]);
            int bb = (R[b] > B[b]);
            if(aa == 0 && bb == 0)
            {
                hi = md;
            }
            else if(aa == 1 && bb == 1)
            {
                lo = md;
            }
            else
                return bb;
        }
        return 1;
    }
}

void merge(vector<int> &arr, int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    
    vector<int> L(n1), R(n2);
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = l;
    
    while (i < n1 && j < n2) {
        if (cmp(L[i], R[j])) 
            arr[k++] = L[i++];
        else 
            arr[k++] = R[j++];
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void Sort(vector<int> &arr, int l, int r) {
    if (l >= r) return;
    
    int mid = l + (r - l) / 2;
    
    Sort(arr, l, mid);
    Sort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        vector<int> order(N);
        iota(order.begin() , order.end() , 0);
        Sort(order , 0 , N - 1);
        for(int i = 0 ; i < N ; i++)
        {
            P[order[i]] = i + 1;
        } 
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        sub = 1;
        vector<int> order(N);
        iota(order.begin() , order.end() , 0);
        Sort(order , 0 , N - 1);
        for(int i = 0 ; i < N ; i++)
        {
            P[order[i]] = i + 1;
        } 
    }
}

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