Submission #720469

#	Time	Username	Problem	Language	Result	Execution time	Memory
720469		nguyentunglam	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	11 ms	316 KiB

mushrooms

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

int count_mushrooms(int n) {
    vector<int> v = {0};
    vector<int> A, B;
    A.push_back(0);
    int T = min(188, n);
    for(int i = 1; i < T; i++) {
        v.push_back(i);
        if (!use_machine(v)) A.push_back(i);
        else B.push_back(i);
        v.pop_back();
    }

    bool ok = 0;
    int tmp = 0;
    if (A.size() < B.size()) swap(A, B), ok = 1;
    int sz = A.size(), cnt = 0;
    for(int i = T; i < n; i += sz) {
        vector<int> ask;
        for(int j = i; j < n && j < i + sz; j++) {
            ask.push_back(A[j - i]);
            ask.push_back(j);
            cnt++;
        }
        tmp += (use_machine(ask) + 1) / 2;
    }
    if (!ok) return A.size() + cnt - tmp;
    return B.size() + tmp;
}

• Subtask 1: 56.7839 / 100