제출 #1193896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193896		dong_gas	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	464 KiB

mushrooms

#include <bits/extc++.h>
using namespace std;
const int MAXN = 2e4 + 24;
int use_machine(vector<int> x);

int f(int n) {
    int b = 0;
    for (int i = 1; i + 1 < n; i += 2) b += use_machine({i, 0, i + 1});
    if ((n & 1)== 0) b += use_machine({0, n - 1});
    return n - b;
}

int count_mushrooms(int n) {
    if (n<=450) return f(n);
    vector<int> a = {0}, b;
    int acnt = 1, bcnt = 0, idx = 1;
    // 물어봐서 개수 더하기
    while (idx < n) {
        vector<int> q, c = (a.size() >= b.size()) ? a : b;
        int qcnt = 0;
        for (int i = 0; i < c.size() && idx < n; i++) {
            q.push_back(c[i]);
            q.push_back(idx++);
            qcnt++;
        }
        // for (auto qq: q) cout << qq << ' ';
        // cout << endl;
        int query = use_machine(q);
        int p = query / 2;
        if (a.size() >= b.size()) {
            if (query & 1) b.push_back(idx - 1), p++;
            else a.push_back(idx - 1);
            acnt += qcnt - p, bcnt += p;
        }
        else {
            if (query & 1) a.push_back(idx - 1), p++;
            else b.push_back(idx - 1);
            acnt += p, bcnt += qcnt - p;
        }
        // cout << acnt << ' ' << bcnt << endl;
    }
    return acnt;
}

• Subtask 1: 80.7143 / 100