Submission #1040933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040933		MeGustaElArroz23	Koala Game (APIO17_koala)	C++14	29 / 100	25 ms	896 KiB

koala

#include "koala.h"

#include<bits/stdc++.h>

#define vi vector<int>
#define pb push_back

using namespace std;


int minValue(int n, int W) { //N=W
    int* A = new int[n];
    int* B = new int[n];
    for (int i=0;i<n;i++) A[i]=1;
    playRound(A,B);
    vi grandes;
    for (int i=0;i<n;i++) if (B[i]==2) grandes.pb(i);

    for (int i=0;i<n;i++) A[i]=0;
    A[grandes[0]]=2;
    A[grandes[1]]=n-2;

    playRound(A,B);
    for (int i=0;i<n;i++) if (i!=grandes[1] && B[i]==0) return i;
}

int maxValue(int n, int W) {
    int* A = new int[n];
    int* B = new int[n];

    vi isgrande(n,1);
    int grandes = n;
    while (grandes>1){
        int c=n%grandes;
        for (int i=0;i<n;i++){
            if (isgrande[i]) A[i]=n/grandes;
            else if (c){
                A[i]=1;
                c--;
            }
            else A[i]=0;
        }

        playRound(A,B);
        for (int i=0;i<n;i++) if (isgrande[i] && A[i]>=B[i]){
            grandes--;
            isgrande[i]=0;
        }
    }
    for (int i=0;i<n;i++) if (isgrande[i]) return i;
    assert(0);
}

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.
    return 0;
}


bool cmp(int a, int b){
    if (a==b) return 0;
    int* A = new int[100];
    int* B = new int[100];

    for (int i=0;i<100;i++) A[i]=0;
    A[a]=A[b]=100;
    // cerr << "q: ";
    // for (int i=0;i<100;i++) cerr << A[i] << ' ';
    playRound(A,B);
    // cerr << endl;
    // for (int i=0;i<100;i++) cerr << B[i] << ' ';
    // cerr << endl;
    return B[a]<=100;
}

void merge(std::vector<int>& vec, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary vectors
    std::vector<int> leftVec(n1);
    std::vector<int> rightVec(n2);

    // Copy data to temporary vectors
    for (int i = 0; i < n1; ++i)
        leftVec[i] = vec[left + i];
    for (int i = 0; i < n2; ++i)
        rightVec[i] = vec[mid + 1 + i];

    // Merge the temporary vectors back into vec[left..right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (cmp(leftVec[i], rightVec[j])) {
            vec[k] = leftVec[i];
            ++i;
        } else {
            vec[k] = rightVec[j];
            ++j;
        }
        ++k;
    }

    // Copy the remaining elements of leftVec, if any
    while (i < n1) {
        vec[k] = leftVec[i];
        ++i;
        ++k;
    }

    // Copy the remaining elements of rightVec, if any
    while (j < n2) {
        vec[k] = rightVec[j];
        ++j;
        ++k;
    }
}

// Merge sort function
void mergeSort(std::vector<int>& vec, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(vec, left, mid);
        mergeSort(vec, mid + 1, right);

        // Merge the sorted halves
        merge(vec, left, mid, right);
    }
}

// Helper function to call mergeSort
void sortVector(std::vector<int>& vec) {
    if (!vec.empty()) {
        mergeSort(vec, 0, vec.size() - 1);
    }
}

void allValues(int n, int W, int *P) {
    if (W == 2*n) {
        vi v(n);
        for (int i=0;i<n;i++) v[i]=i;
        sortVector(v);
        for (int i=0;i<n;i++) P[v[i]]=i+1;
        return;
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:16:8: warning: control reaches end of non-void function [-Wreturn-type]
   16 |     vi grandes;
      |        ^~~~~~~

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