제출 #448286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448286		dxz05	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	3 ms	200 KiB

mushrooms

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

using namespace std;

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 = 140;

    vector<int> A = {0}, B;
    for (int i = 1; i <= 2; i++){
	    if (use_machine({0, i})) B.push_back(i); else
	        A.push_back(i);
	}

    for (int i = 3; i < min(n, 2 * k - 1); i += 2){
        if (i + 1 == n){
            if (use_machine({0, i})) B.push_back(i); else
                A.push_back(i);
            continue;
        }

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

    int beg = 2 * k - 1;

    k = max(A.size(), B.size());

    bool ok = A.size() >= B.size();

    int ans = A.size();
    for (int i = beg; i < n; i++){
        vec.clear();
        for (int j = i; j < min(n, i + k); j++){
            vec.push_back(ok ? A[j - i] : B[j - i]);
            vec.push_back(j);
        }
        i += k - 1;

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

	return ans;
}

• Subtask 1: 0 / 100