Submission #413115

#	Time	Username	Problem	Language	Result	Execution time	Memory
413115		phathnv	Counting Mushrooms (IOI20_mushrooms)	C++17	88.28 / 100	12 ms	368 KiB

mushrooms

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

int count_mushrooms(int n) {
    vector<int> type[2];
    int flag = 0, cur = 1, k = -1, best = 1e9, cnt[2] = {0, 0};
    type[0].push_back(0);
    for(int i = 2; i <= n; i++) {
        int numQ = 2 + i - 2 + (n - (2 * i - 1) + i - 1) / i;
        if (numQ < best) {
            best = numQ;
            k = i;
        }
    }
    //cerr << "k: " << k << endl;
    while (cur < n) {
        if (type[0].size() < type[1].size()) {
            flag ^= 1;
            swap(type[0], type[1]);
            swap(cnt[0], cnt[1]);
        }
        if ((int) type[0].size() < k) {
            int num = min(2, min(n - cur, (int) type[0].size()));
            vector<int> a;
            for(int i = 0; i < num; i++) {
                a.push_back(cur + i);
                a.push_back(type[0][i]);
            }
            int x = use_machine(a);
            for(int i = 0; i < num; i++)
                type[(x >> i) & 1].push_back(cur + i);
            cur += num;
        } else {
            int num = min(n - cur, (int) type[0].size());
            vector<int> a;
            for(int i = 0; i < num; i++) {
                a.push_back(cur + i);
                a.push_back(type[0][i]);
            }
            int x = use_machine(a);
            type[x & 1].push_back(cur);
            cnt[1] += x / 2;
            cnt[0] += (num - 1) - x / 2;
            cur += num;
        }
    }
    if (flag) {
        flag ^= 1;
        swap(type[0], type[1]);
        swap(cnt[0], cnt[1]);
    }
    return cnt[0] + type[0].size();
}

• Subtask 1: 88.2812 / 100