Submission #448412

#	Time	Username	Problem	Language	Result	Execution time	Memory
448412		dxz05	버섯 세기 (IOI20_mushrooms)	C++14	82.18 / 100	11 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

int f(int n, int k){
    return k + (n + k - 2) / k - 2;
}

int count_mushrooms(int n) {
    if (n <= 227){
        int ans = 1;
        for (int i = 1; i < n; i++){
            ans += 1 - use_machine({0, i});
        }
        return ans;
    }

    vector<int> vec;
    int k = 85;

    vector<int> A = {0}, B;

    int pos = 1;
    while (A.size() < 2 && B.size() < 2){
        int res = use_machine({0, pos});
        if (res == 0) A.push_back(pos); else
            B.push_back(pos);
        pos++;
    }

    for (int it = 0; it < k - 2; it++){
        if (pos + 1 == n){
            if (use_machine({0, pos})) B.push_back(pos); else
                A.push_back(pos);
            pos++;
            break;
        }

        if (A.size() >= 2){
            vec = {pos, A[0], pos + 1, A[1]};
            int res = use_machine(vec);
            if (res & 1) B.push_back(pos); else
                A.push_back(pos);
            if (res & 2) B.push_back(pos + 1); else
                A.push_back(pos + 1);
        } else {
            vec = {pos, B[0], pos + 1, B[1]};
            int res = use_machine(vec);
            if (res & 1) A.push_back(pos); else
                B.push_back(pos);
            if (res & 2) A.push_back(pos + 1); else
                B.push_back(pos + 1);
        }

        pos += 2;
    }

    int ans = A.size();
    while (pos < n){
        vec.clear();
        k = max(A.size(), B.size());
        bool ok = A.size() >= B.size();

        for (int j = pos; j < min(n, pos + k); j++){
            vec.push_back(j);
            vec.push_back(ok ? A[j - pos] : B[j - pos]);
        }

        int res = use_machine(vec);
        if (ok) ans += vec.size() / 2 - (res + 1) / 2; else
            ans += (res + 1) / 2;

        if (res % 2){
            if (ok) B.push_back(pos); else
                A.push_back(pos);
        }

        pos += k;
    }

	return ans;
}

• Subtask 1: 82.1818 / 100