제출 #407391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407391		qwerasdfzxcl	코알라 (APIO17_koala)	C++14	100 / 100	71 ms	436 KiB

koala

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

using namespace std;

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.
    int B[100]={0}, R[100]={0};
    B[0] = 1;
    playRound(B, R);
    for (int i=0;i<N;i++) if (B[i]>=R[i]) return i;
    return 0;
}

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.
    int B[100] = {0}, R[100] = {0};
    for (int i=0;i<N;i++) B[i] = 1;
    playRound(B, R);
    int prv = 1;
    for (int z=1;z<4;z++){
        int cnt=0;
        for (int i=0;i<N;i++) if (R[i]>prv) cnt++;
        for (int i=0;i<N;i++){
            if (R[i]<=prv) B[i] = 0;
            else B[i] = W/cnt;
        }
        prv = W/cnt;
        playRound(B, R);
    }
    for (int i=0;i<N;i++) if (R[i]==12) return i;
    assert(0);
    return 0;
}

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.
    int B[100] = {0}, R[100] = {0};
    B[0] = B[1] = 4;
    playRound(B, R);
    if (min(R[0], R[1])>=5){
        B[0] = B[1] = 8;
        playRound(B, R);
        if (R[0]>R[1]) return 0;
        return 1;
    }
    else if (max(R[0], R[1])<=4){
        B[0] = B[1] = 2;
        playRound(B, R);
        assert(R[0]<=2 || R[1]<=2);
        if (R[0]<=2 && R[1]<=2){
            B[0] = 1, B[1] = 0;
            playRound(B, R);
            if (B[0]>=R[0]) return 1;
            return 0;
        }
        if (R[0]>2) return 0;
        return 1;
    }
    if (R[0]>4) return 0;
    return 1;
}

void dnc(int l, int r, vector<int> &v, int *P){
    //printf("%d %d\n", l, r);
    assert(l<=r);
    if (l==r){
        P[v[0]] = l; return;
    }
    int cur = 1;
    int B[100] = {0}, R[100] = {0};
    while(true){
        cur++;
        for (auto &x:v) B[x]++;
        int idx = r, val=0;
        for (;idx>=l;idx--){
            if (val+cur>r-l+1) break;
            val += cur;
        }
        int pt1=1, pt2=idx;
        for (;pt1+cur-1<l && pt2>=l;pt1 += cur, pt2--){
            int tmp = 0;
            for (int i=0;i<cur-1;i++) tmp += pt1+i;
            if (tmp>=pt2)break;
        }
        if (pt2>=l) break;
    }
    //printf("%d\n", B[v[0]]);
    //for (int i=0;i<100;i++) printf("%d ", B[i]);
    //printf("\n");
    playRound(B, R);
    //for (int i=0;i<100;i++) printf("%d ", R[i]);
    //printf("\n");
    vector<int> v1, v2;
    for (auto &x:v){
        if (R[x]>B[x]) v2.push_back(x);
        else v1.push_back(x);
    }
    dnc(l, l+v1.size()-1, v1, P);
    dnc(l+v1.size(), r, v2, P);
}

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.
        bool chk[100] = {0};
        int B[100] = {0}, R[100] = {0};
        for (int k=N;k>=2;k--){
            for (int i=0;i<N;i++) B[i] = 0;
            int prv = W/k;
            for (int i=0;i<N;i++) if (!chk[i]) B[i] = prv;
            playRound(B, R);
            while(true){
                int cnt=0;
                for (int i=0;i<N;i++) if (R[i]>prv) cnt++;
                assert(cnt);
                if (cnt==1){
                    for (int i=0;i<N;i++) if (R[i]>prv) P[i] = k, chk[i] = 1;
                    break;
                }
                for (int i=0;i<N;i++){
                    if (R[i]>prv) B[i] = W/cnt;
                    else B[i] = 0;
                }
                playRound(B, R);
            }
        }
        for (int i=0;i<N;i++) if (!chk[i]) P[i] = 1;
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        int B[100] = {0}, R[100] = {0};
        for (int i=0;i<N;i++) P[i] = 0;
        for (int z=1;z<=50;z++){
            int cnt=0;
            for (int i=0;i<N;i++){
                if (P[i]) B[i] = 1;
                else if (cnt<z) B[i] = 1, cnt++;
            }
            playRound(B, R);
            for (int i=0;i<N;i++) if (!P[i] && R[i]<=B[i]) P[i] = z;
        }
        vector<int> v;
        for (int i=0;i<N;i++) if (!P[i]) v.push_back(i);
        dnc(51, 100, v, P);
    }
}

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