Submission #697932

#	Time	Username	Problem	Language	Result	Execution time	Memory
697932		sharaelong	Koala Game (APIO17_koala)	C++17	29 / 100	59 ms	336 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#include <ostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 100;

int B[MAX_N], R[MAX_N];

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.
    memset(B, 0, sizeof B);
    B[0] = 1;
    playRound(B, R);
    int zero_pos = find(R, R+N, 0) - R;
    return zero_pos;
}

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.

    for (int i=0; i<N; ++i) B[i] = 1;
    playRound(B, R);
    vector<int> half_large;
    for (int i=0; i<N; ++i) {
        if (R[i] == 2) half_large.push_back(i);
    }
    assert(half_large.size() == 50);

    memset(B, 0, sizeof B);
    for (int i: half_large) B[i] = 2;
    playRound(B, R);
    vector<int> quarter_large;
    for (int i=0; i<N; ++i) {
        if (R[i] == 3) quarter_large.push_back(i);
    }

    memset(B, 0, sizeof B);
    for (int i: quarter_large) B[i] = 4;
    playRound(B, R);
    vector<int> ninetyone_large;
    for (int i=0; i<N; ++i) {
        if (R[i] > 1) ninetyone_large.push_back(i);
    }

    memset(B, 0, sizeof B);
    for (int i: ninetyone_large) B[i] = 11;
    playRound(B, R);
    return find(R, R+N, 12) - R;
}

void sub3_helper(int x) {
    memset(B, 0, sizeof B);
    B[0] = B[1] = x;
    playRound(B, R);
}

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.
    sub3_helper(4);
    if (R[0] == R[1]) {
        if (R[0] == 0) {
            sub3_helper(2);
            if (R[0] != R[1]) {
                cout << "2 ";
                return R[0] < R[1];
            }
            sub3_helper(1);
            cout << "1 ";
            return R[0] < R[1];
        } else {
            sub3_helper(8);
            cout << "8 ";
            return R[0] < R[1];
        }
    } else {
        cout << "4 ";
        return R[0] < R[1];
    }
}

void sub4_helper(int i, int j) {
    B[i] = B[j] = 100;
    playRound(B, R);
    B[i] = B[j] = 0;
}

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> ord = { 0 };
        for (int i=1; i<N; ++i) {
            int l = 0, r = i; // bar model
            while (l < r) {
                int mid = (l+r) / 2;
                sub4_helper(ord[mid], i);
                if (R[ord[mid]] < R[i]) {
                    l = mid+1;
                } else {
                    r = mid;
                }
            }
            vector<int> tmp;
            for (int i=0; i<l; ++i) tmp.push_back(ord[i]);
            tmp.push_back(i);
            for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]);
            ord = tmp;
        }
        for (int i=0; i<N; ++i) P[ord[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 allValues(int, int, int*)':
koala.cpp:117:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]);
      |                           ~^~~~~~~~~~~

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