제출 #147216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147216		dolphingarlic	Koala Game (APIO17_koala)	C++14	43 / 100	71 ms	784 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
 
int B[100], R[100];
 
/*
HELPER FUNCTIONS
*/
 
bool compare(int a, int b, int N, int W) {
    fill(B, B + N, 0);
    B[a] = B[b] = W;
    playRound(B, R);
    return (R[b] > W);
}
 
vector<int> mergesort(vector<int> v, int N, int W) {
    if (v.size() == 1) return v;
 
    vector<int> a, b;
    a.insert(a.begin(), v.begin(), v.begin() + (v.size() + 1) / 2);
    b.insert(b.begin(), v.begin() + (v.size() + 1) / 2, v.end());
    a = mergesort(a, N, W), b = mergesort(b, N, W);
 
    vector<int> sorted;
    int aptr = 0, bptr = 0;
    while (aptr < a.size() && bptr < b.size()) {
        if (compare(a[aptr], b[bptr], N, W))
            sorted.push_back(a[aptr++]);
        else
            sorted.push_back(b[bptr++]);
    }
    sorted.insert(sorted.end(), a.begin() + aptr, a.end());
    sorted.insert(sorted.end(), b.begin() + bptr, b.end());
 
    return sorted;
}
 
/*
BEGIN ACTUAL FUNCTIONS
*/
 
int minValue(int N, int W) {
    // Assign a single stone to the first cup
    // If Koala picks that cup, it is not the smallest and some other cup has 0
    // Otherwise, cup 0 is the smallest cup
    // Uses 1 turn
    fill(B, B + N, 0);
    fill(R, R + N, 0);
    B[0] = 1;
    playRound(B, R);
    if (R[0] < 2)
        return 0;
    else {
        FOR(i, 1, N)
        if (!R[i]) return i;
    }
    return -1;
}
 
int maxValue(int N, int W) {
    // Binary search for the max value
    // Uses like 7 turns
    vector<int> v;
    FOR(i, 0, N)
    v.push_back(i);
    while (v.size() != 1) {
        int k = W / v.size();
        fill(B, B + N, 0);
        for (int i : v) B[i] = k;
        playRound(B, R);
        v.clear();
        FOR(i, 0, N)
        if (R[i] > k) v.push_back(i);
    }
    return v[0];
}
 
int greaterValue(int N, int W) {
    // Assign positions 0 and 1 x stones until Koala treats them differently
    // Binary search for x:
    // If both 0 and 1 get > x stones, increase x
    // If both 0 and 1 get < x stones, decrease x
    // Notice how x <= 9 because sum(9..17) > 100
    // Uses like 4 turns
    int l = 1, r = 9;
    while (l != r) {
        int mid = (l + r) / 2;
        B[0] = B[1] = mid;
        playRound(B, R);

        if (R[0] > mid && R[1] > mid) l = mid + 1;
        else if (R[0] <= mid && R[1] <= mid) r = mid;
        else if (R[0] > R[1]) return 0;
        else return 1;
    }
    return -1;
}
 
void allValues(int N, int W, int *P) {
    if (W == 2 * N) {
        // Assign indices i and j 100 stones each to check whether P[i] > P[j]
        // Use merge sort to get O(Nlog(N)) <= 700 turns
        vector<int> v;
        FOR(i, 0, N)
        v.push_back(i);
        vector<int> sorted = mergesort(v, N, W / 2);
        FOR(i, 0, N)
        P[sorted[i]] = i + 1;
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

컴파일 시 표준 에러 (stderr) 메시지

koala.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
koala.cpp: In function 'std::vector<int> mergesort(std::vector<int>, int, int)':
koala.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (aptr < a.size() && bptr < b.size()) {
            ~~~~~^~~~~~~~~~
koala.cpp:32:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (aptr < a.size() && bptr < b.size()) {
                               ~~~~~^~~~~~~~~~

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