제출 #226177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226177		theStaticMind	코알라 (APIO17_koala)	C++14	70 / 100	117 ms	512 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;

int B[105], R[105];

int minValue(int N, int W) {

    for(int i = 0; i < N; i++) B[i] = 1;

    playRound(B, R);

    for(int i = 0; i < N; i++) B[i] = 0;
    for(int i = 0; i < N; i++){
        if(R[i] > 1){
            B[i] = 1;
            break;
        }
    }

    playRound(B, R);

    for(int i = 0; i < N; i++){
        if(R[i] <= B[i]) return i;
    }
    assert(0);

}


int maxValue(int N, int W) {
    bool rem[105];
    for(int i = 0; i < N; i++) rem[i] = true;
    auto recalc = [&](){
        int sum = 0;
        for(int i = 0; i < N; i++) if(rem[i]) sum++;
        for(int i = 0; i < N; i++){
            if(rem[i]) B[i] = W / sum;
            else B[i] = 0;
        }
    };

    for(int t = 0; t < 4; t++){
        recalc();
        playRound(B, R);
        for(int i = 0; i < N; i++){
            if(R[i] <= B[i]) rem[i] = false;
        }
    }

    for(int i = 0; i < N; i++){
        if(rem[i]) return i;
    }
    assert(0);
}

bool comp(int x, int y){
    vector<int> T = {1, 2, 3, 5, 8};
    int l = 0, r = 4;

    while(l <= r){
        int mid = (l + r) / 2;

        for(int i = 0; i < 100; i++) B[i] = 0;
        B[x] = B[y] = T[mid];
        playRound(B, R);

        if(R[x] <= B[x] && R[y] <= B[y]) r = mid - 1;
        else if(R[x] > B[x] && R[y] > B[y]) l = mid + 1;
        else{
            return R[x] <= B[x];
        }

    }
    assert(0);
    return 0;
}

bool comp2(int x, int y){
  for(int i = 0; i < 100; i++) B[i] = 0;
  B[x] = B[y] = 100;
  playRound(B, R);
  return R[x] <= B[x];
}

int greaterValue(int N, int W) {
    if(comp(0, 1)) return 1;
    else return 0;
}


vector<int> mergesort(int l, int r, const function<bool(int x, int y)>& cmp){
    if(l == r) return {l};
    vector<int> L = mergesort(l, (l + r) / 2, cmp), R = mergesort((l + r) / 2 + 1, r, cmp);
    vector<int> ret;

    int a = 0, b = 0;
    while(a < L.size() || b < R.size()){
        if(b == R.size() || (a != L.size() && cmp(L[a], R[b]))) ret.push_back(L[a++]);
        else ret.push_back(R[b++]); 
    }
    return ret;
}

void allValues(int N, int W, int *P) {
    vector<int> ptr(N);
    for(int i = 0; i < N; i++) ptr[i] = i;
    if (W == 2*N) {
        ptr = mergesort(0, N - 1, comp2);
    } 
    else {
        ptr = mergesort(0, N - 1, comp);
    }
    for(int i = 0; i < N; i++){
        P[ptr[i]] = i + 1;
    }
}

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

koala.cpp: In function 'std::vector<int> mergesort(int, int, const std::function<bool(int, int)>&)':
koala.cpp:98:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(a < L.size() || b < R.size()){
           ~~^~~~~~~~~~
koala.cpp:98:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(a < L.size() || b < R.size()){
                           ~~^~~~~~~~~~
koala.cpp:99:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(b == R.size() || (a != L.size() && cmp(L[a], R[b]))) ret.push_back(L[a++]);
            ~~^~~~~~~~~~~
koala.cpp:99:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(b == R.size() || (a != L.size() && cmp(L[a], R[b]))) ret.push_back(L[a++]);
                              ~~^~~~~~~~~~~

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