Submission #842404

#	Time	Username	Problem	Language	Result	Execution time	Memory
842404		Tob	Koala Game (APIO17_koala)	C++14	43 / 100	48 ms	600 KiB

koala

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

using namespace std;

int minValue(int N, int W) {
    int arr[100] = {0}, r[100];
    arr[0] = 1;
    playRound(arr, r);
    for (int i = 1; i < N; i++) if (r[i] == 0) return i;
    return 0;
}

int maxValue(int N, int W) {
    int arr[100] = {0}, r[100];
    vector <int> v;
    for (int i = 0; i < N; i++) {
        v.push_back(i);
    }
    while (v.size() > 1) {
        for (int i = 0; i < N; i++) arr[i] = 0;
        int siz = v.size();
        for (int i = 0; i < siz; i++) arr[v[i]] = N/siz;
        playRound(arr, r);
        v.clear();
        for (int i = 0; i < N; i++) if (r[i] > N/siz) v.push_back(i);
    }
    return v[0];
}

int greaterValue(int N, int W) {
    int arr[100] = {0}, r[100];
    int lo = 1, hi = 9;
    while (lo <= hi) {
        int mid = (lo + hi + 1) / 2;
        fill(arr, arr+N, 0);
        arr[0] = arr[1] = mid;
        playRound(arr, r);
        if ((r[0] > mid) != (r[1] > mid)) return (r[0] < r[1]);
        if (r[0] <= mid && r[1] <= mid) hi = mid-1;
        else lo = mid;
    }

    return 0;
}

bool Cmp(int x, int y, int N) {
    int arr[100] = {0}, r[100];
    arr[x] = arr[y] = N;
    playRound(arr, r);
    return r[x] < r[y];
}
void Sort(vector <int>& v, int N) {
    int siz = v.size();
    if (siz == 1) return;
    vector <int> a, b;
    for (int i = 0; i < siz/2; i++) a.push_back(v[i]);
    for (int i = siz/2; i < siz; i++) b.push_back(v[i]);
    v.clear();
    Sort(a, N); Sort(b, N);
    //for (int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << " -  ";
    //for (int i = 0; i < b.size(); i++) cout << b[i] << " "; cout << "\n";
    int x = 0, y = 0;
    for (; x < a.size() && y < b.size();) {
        if (Cmp(a[x], b[y], N)) v.push_back(a[x++]);
        else v.push_back(b[y++]);
    }
    for (; x < a.size(); x++) v.push_back(a[x]);
    for (; y < b.size(); y++) v.push_back(b[y]);
    //for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << "\n";
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector <int> v;
        for (int i = 0; i < N; i++) v.push_back(i);
        Sort(v, N);
        for (int i = 0; i < N; i++) P[v[i]] = i+1;
    } 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 'void Sort(std::vector<int>&, int)':
koala.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (; x < a.size() && y < b.size();) {
      |            ~~^~~~~~~~~~
koala.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (; x < a.size() && y < b.size();) {
      |                            ~~^~~~~~~~~~
koala.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (; x < a.size(); x++) v.push_back(a[x]);
      |            ~~^~~~~~~~~~
koala.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (; y < b.size(); y++) v.push_back(b[y]);
      |            ~~^~~~~~~~~~

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