제출 #321977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321977		grt	버섯 세기 (IOI20_mushrooms)	C++17	59.16 / 100	11 ms	620 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int B = 250;
vi a, b;

int use_machine(vi x);

int count_mushrooms(int n) {
    srand(time(NULL));
    if(n == 1) return 1;
    vi v(n-1);
    a = {};
    b = {};
    for(int i = 1; i < n; ++i) v[i - 1] = i;
    random_shuffle(v.begin(), v.end());
    a.PB(0);
    for(int i = 0; i < min(n - 1, B); ++i) {
        int w = use_machine({0, v[i]});
        if(w == 1) b.PB(v[i]);
        else a.PB(v[i]);
    }
    int ans = (int)a.size();
    bool inv = 0;
    if((int)a.size() < (int)b.size()) {
        swap(a, b);
        inv = 1;
    }
    for(int i = B; i < n - 1; i++) {
        vi s = {};
        int nxt = 0, all = 0;
        int last = 0;
        for(int j = i; j < min(n - 1, i + (int)a.size()); ++j) {
            s.PB(a[nxt++]);
            s.PB(v[j]);
            all++;
            last = j;
        }
        int w = use_machine(s);
        if(!inv) {
            int cntB = w / 2 + (w % 2);
            ans += all - cntB;
            if(w%2 == 0) {
                a.PB(v[last]);
            }
        } else {
            ans += w/2 + (w%2);
            if(w % 2 == 0) {
                a.PB(v[last]);
            }
        }
        i = last;
    }
    return ans;
}

• Subtask 1: 59.1623 / 100