oj.uz

Submission #1040933

# Submission time Handle Problem Language Result Execution time Memory
1040933 2024-08-01T12:33:46 Z MeGustaElArroz23 Koala Game (APIO17_koala) C++14
29 / 100
 25 ms 896 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 516 KB Output is correct
4 Correct 5 ms 476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 464 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 22 ms 856 KB Output is correct
4 Correct 21 ms 856 KB Output is correct
5 Correct 21 ms 856 KB Output is correct
6 Correct 21 ms 776 KB Output is correct
7 Correct 21 ms 876 KB Output is correct
8 Correct 25 ms 844 KB Output is correct
9 Correct 24 ms 848 KB Output is correct
10 Correct 22 ms 856 KB Output is correct
11 Correct 25 ms 760 KB Output is correct
12 Correct 12 ms 600 KB Output is correct
13 Correct 21 ms 856 KB Output is correct
14 Correct 19 ms 600 KB Output is correct
15 Correct 19 ms 856 KB Output is correct
16 Correct 23 ms 600 KB Output is correct
17 Correct 18 ms 600 KB Output is correct
18 Correct 19 ms 716 KB Output is correct
19 Correct 19 ms 816 KB Output is correct
20 Correct 19 ms 600 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -