제출 #303459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303459		dacin21	버섯 세기 (IOI20_mushrooms)	C++17	79.86 / 100	12 ms	408 KiB

mushrooms

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

using ll = long long;
int count_mushrooms(int n) {
    auto use = [&](vector<int> const&x){ return use_machine(x);};
    vector<char> s(n);
    // first find 3 equal ones
    const int k = min(n, 5);
    for(int i=1; i<k; ++i){
        if(use({0, i})){
            ++s[i];
        }
    }
    if(n == k){
        return count(s.begin(), s.end(), 0);
    }
    // now find sqrt(n) equal ones
    int i = k;
    {
        int me = 0;
        if(2*accumulate(s.begin(), s.begin()+k, 0) > k){
            me = 1;
        }
        vector<int> pool;
        for(int j=0; j<k; ++j){
            if(s[j] == me) pool.push_back(j);
        }
        assert(pool.size() >= 3);
        const int l = min(n, k + 2*int(sqrt(n)));
        //debug << named(l) << "\n";
        while(i<l && i+2 < n){
            const int x = use({i, pool[0], i+1, pool[1]});
            s[i] = me ^ (x%2==1);
            s[i+1] = me ^ (x/2==1);
            i += 2;
        }
    }
    // now count
    int ans = count(s.begin(), s.begin()+i, 0);
    //debug << k << " : " << decltype(s)(s.begin(), s.begin()+i) << "\n";
    {
        int me = 0;
        if(2*accumulate(s.begin(), s.begin()+i, 0) > i){
            me = 1;
        }
        vector<int> pool;
        for(int j=0; j<i; ++j){
            if(s[j] == me) pool.push_back(j);
        }
        //debug << named(pool.size()) << "\n";
        while(i < n){
            const int U = min<int>(n-i, pool.size()-1);
            vector<int> q(1, pool[0]);
            for(int j=0; j<U; ++j){
                q.push_back(i++);
                q.push_back(pool[j+1]);
            }
            int r = use(q)/2;
            if(me == 0) r = U-r;
            ans += r;
        }
    }
    return ans;
}

• Subtask 1: 79.8587 / 100