제출 #1336205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336205		itaykarny	코알라 (APIO17_koala)	C++20	65 / 100	79 ms	1068 KiB

koala

#include "koala.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<set>
#include<map>
#include<queue>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll n = 100;
ll w = 100;

int b[n], r[n];
int p[n];

void solve(vll& ind, ll offset,ll go, bool need_left) {
    ll m = ind.size();
    if (m == 0) { return; }
    if (m == 1) {
        p[ind[0]] = offset;
        return;
    }
    ll put = 1 + min(go, (offset / m));
    for (ll i = 0; i < n; i++) {
        b[i] = 0, r[i] = 0;
    }
    for (ll i = 0; i < m; i++) {
        b[ind[i]] = put;
    }
    playRound(b, r);
    vll left, right;
    for (ll i = 0; i < m; i++) {
        if (r[ind[i]] > b[ind[i]]) {
            right.push_back(ind[i]);
        }
        else {
            left.push_back(ind[i]);
        }
    }
    if (need_left) { solve(left, offset, go, need_left); }
    solve(right, offset + left.size(), go + 1, need_left);
}

ll help(vll& ind, ll offset, ll go) {
    ll m = ind.size();
    ll put = 1 + min(go, (offset / m));
    for (ll i = 0; i < n; i++) {
        b[i] = 0, r[i] = 0;
    }
    for (ll i = 0; i < m; i++) {
        b[ind[i]] = put;
    }
    playRound(b, r);
    vll left, right;
    ll zero = -1, one = -1;
    for (ll i = 0; i < m; i++) {
        if (r[ind[i]] > b[ind[i]]) {
            if (ind[i] == 0) { zero = 1; }
            if (ind[i] == 1) { one = 1; }
            right.push_back(ind[i]);
        }
        else {
            if (ind[i] == 0) { zero = 0; }
            if (ind[i] == 1) { one = 0; }
            left.push_back(ind[i]);
        }
    }
    if (one < zero) { return 0; }
    if (zero < one) { return 1; }
    if (one == 1) {
        return help(right, offset + left.size(), go + 1);
    }
    else {
        return help(left, offset, go);
    }
}

int minValue(int N, int W) {
    for (ll i = 0; i < n; i++) {
        b[i] = 0, r[i] = 0;
    }
    b[0] = 1;
    playRound(b, r);
    for (ll i = 0; i < n; i++) {
        if (r[i] == 0) { return i; }
    }
}

int maxValue(int N, int W) {
    vll ind(n);
    for (ll i = 0; i < n; i++) {
        ind[i] = i;
    }
    for (ll i = 0; i < n; i++) {
        p[i] = 0;
    }
    solve(ind, 1, 0, false);
    for (ll i = 0; i < n; i++) {
        if (p[i] == n) { 
            return i; 
        }
    }
}

int greaterValue(int N, int W) {
    vll ind(n);
    for (ll i = 0; i < n; i++) {
        ind[i] = i;
    }
    return help(ind, 1, 0);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vll ind(n);
        for (ll i = 0; i < n; i++) {
            ind[i] = i;
        }
        solve(ind, 1, 0, true);
        for (ll i = 0; i < n; i++) {
            P[i] = p[i];
        }
    } else {
        vll ind(n);
        for (ll i = 0; i < n; i++) {
            ind[i] = i;
        }
        solve(ind, 1, 0, true);
        for (ll i = 0; i < n; i++) {
            P[i] = p[i];
        }
    }
}

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

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

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