제출 #835434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835434		TheSahib	버섯 세기 (IOI20_mushrooms)	C++14	56.93 / 100	9 ms	364 KiB

mushrooms

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

using namespace std;

const int BLOCK = 100;

vector<int> A, B;

int count_mushrooms(int n) {
    if(n <= BLOCK * 2){
        int ans = 1;
        for (int i = 1; i < n; i++)
        {
            ans += use_machine({0, i}) == 0;
        }
        return ans;
    }
    A.push_back(0);
    bool swp = false;
    for (int i = 1; i < BLOCK * 2; ++i)
    {
        bool b = use_machine({0, i}) == 1;
        if(b){
            B.push_back(i);
        }
        else{
            A.push_back(i);
        }
    }
    int ans = A.size();
    int cnt = 0;
    if(A.size() < B.size()) {
        swp = true;
        swap(A, B);
    }
    for (int i = BLOCK * 2; i < n; i += A.size())
    {
        vector<int> v;
        for(int j = i; j < min(n, i + int(A.size())); ++j){
            v.push_back(A[j - i]);
            v.push_back(j);
        }
        cnt += (use_machine(v) + 1) / 2;
    }
    if(!swp){
        cnt = (n - BLOCK * 2) - cnt;
    }
    ans += cnt;
    return ans;
}

• Subtask 1: 56.927 / 100