제출 #701292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701292		Abrar_Al_Samit	코알라 (APIO17_koala)	C++17	86 / 100	53 ms	344 KiB

koala

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

using namespace std;

int lim[101];
int minValue(int N, int W) {
    int B[N], R[N];
    for(int i=0; i<N; ++i) {
        B[i] = R[i] = 0;
    }
    B[0] = 1;
    playRound(B, R);

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

int maxValue(int N, int W) {
    int B[N] = {0}, R[N] = {0};

    set<int>s;
    for(int i=0; i<N; ++i) {
        s.insert(i);
    }

    while(s.size()>1) {
        int val = W / s.size();

        memset(B, 0, sizeof B);
        memset(R, 0, sizeof R);

        for(int x : s) {
            B[x] = val;
        }
        playRound(B, R);

        set<int>new_s;
        for(int i=0; i<N; ++i) if(R[i]>B[i]) {
            if(s.count(i)) new_s.insert(i);
        }
        s = new_s;
    }
    return *s.begin();    
}

int greaterValue(int N, int W) {
    int B[N] = {0}, R[N] = {0};

    int l = 1, r = 13;

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

        B[0] = B[1] = mid;
        playRound(B, R);

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

void solve(set<int>s, int *P, int mx, int N, int W) {
    if(s.size()==1) {
        P[*s.begin()] = mx;
        return;
    }
    int B[N] = {0}, R[N] = {0};
    int val = W / s.size();
    val = min(val, lim[mx]);

    for(int j : s) {
        B[j] = val;
    }
    playRound(B, R);

    set<int>bigger;
    for(int j : s) {
        if(R[j]>B[j]) {
            bigger.insert(j);
        }
    }
    for(int x : bigger) {
        s.erase(x);
    }

    solve(bigger, P, mx, N, W);
    mx -= bigger.size();
    solve(s, P, mx, N, W);
}
bool cmp(int i, int j) {
    int B[100] = {0}, R[100];

    B[i] = B[j] = 100;
    playRound(B, R);

    if(R[i]>B[i]) return false;
    return true;
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector<int>order(N);
        iota(order.begin(), order.end(), 0);

        sort(order.begin(), order.end(), cmp);
        for(int i=0; i<N; ++i) {
            P[order[i]] = i+1;
        }
    } else {
        int S = 0;
        for(int i=1, cur=1; i<=N; ++i) {
            if(i>S) S += cur, ++cur;
            lim[i] = cur-2;
        }

        set<int>s;
        for(int i=0; i<N; ++i) {
            s.insert(i);
        }
        solve(s, P, N, N, W);
    }
}

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

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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