제출 #586691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586691		PiejanVDC	버섯 세기 (IOI20_mushrooms)	C++17	69.75 / 100	10 ms	340 KiB

mushrooms

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

int use_machine(vector<int> x);

const int g = 70;

int count_mushrooms(int n) {
    int A = 1, B = 0;
    vector<int>a,b;
    a.push_back(0);
    int p = 1;
    while(A < g && B < g) {
        if(p == n)
            return A;
        if(!use_machine({0, p}))
            A++, a.push_back(p);
        else
            B++, b.push_back(p);
        p++;
    }
    while(A + B < n) {
        if(a.size() > b.size()) {
            int lim = min((int)a.size(), n-p);
            vector<int>ask;
            for(int i = 0 ; i < lim ; i++) {
                ask.push_back(a[i]);
                ask.push_back(p);
                p++;
            }
            int x = use_machine(ask);
            x++;
            B += x/2;
            if(x&1)
                a.push_back(p-1);
            A += lim - x/2;
        } else {
            int lim = min((int)b.size(), n-p);
            vector<int>ask;
            for(int i = 0 ; i < lim ; i++) {
                ask.push_back(b[i]);
                ask.push_back(p);
                p++;
            }
            int x = use_machine(ask);
            x++;
            A += x/2;
            if(x&1)
                b.push_back(p-1);
            B += lim - x/2;
        }
    }
    return A;
}

• Subtask 1: 69.7531 / 100