제출 #494952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494952		PiejanVDC	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	200 KiB

mushrooms

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

int count_mushrooms(int n) {
    int a=1,b=0;
    int goal = (n+1)/2;
    int i=1;
    vector<int>posA = {0},posB;
    while(a < goal && b < goal) {
        int x = use_machine({0,i});
        if(x) b++,posB.push_back(i);
        else a++,posA.push_back(i);
        i++;
    }
    bool use = (a == goal ? 1 : 0);
    int ans = 1;
    while(i < n) {
        vector<int>check;
        int p = 0;
        int sz = n - i;
        for(int k = 0 ; k < min(goal + goal - 1, 2*sz+1) ; k++) {
            if(k&1) check.push_back(i++);
            else check.push_back((use ? posA[p++] : posB[p++]));
        }
        int cnt = use_machine(check);
        ans += goal - 1 - cnt/2;
        assert(goal - 1 - cnt/2 >= 0);
    }
    return ans;
}

• Subtask 1: 0 / 100