제출 #413132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413132		phathnv	버섯 세기 (IOI20_mushrooms)	C++17	92.62 / 100	12 ms	456 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, rem = n - 2 * i - 1, cnt = 2 * i - 1;
        while (rem > 0) {
            rem -= (cnt + 1) / 2;
            cnt++;
            numQ++;
        }
        if (numQ < best) {
            best = numQ;
            k = i;
        }
    }
    cerr << "k: " << k << endl;
    k--;
    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: 92.623 / 100