제출 #303460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303460		dacin21	버섯 세기 (IOI20_mushrooms)	C++17	92.62 / 100	13 ms	432 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 2 equal ones
    const int k = min(n, 3);
    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() >= 2);
        const int l = min(n, k + int(1.1*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 = 0;
    //debug << k << " : " << decltype(s)(s.begin(), s.begin()+i) << "\n";
    {
        array<vector<int>, 2> occ;
        for(int j=0; j<i; ++j){
            occ[s[j]].push_back(j);
        }
        //debug << named(occ) << "\n";
        while(i < n){
            const int me = (occ[1].size()>occ[0].size());
            auto&pool = occ[me];
            const int U = min<int>(n-i, occ[me].size()-1);
            //const int U = min<int>(n-i, (occ[0].size()+occ[1].size()+1)/2-1);
            vector<int> q(1, pool[0]);
            for(int j=0; j<U; ++j){
                q.push_back(i++);
                q.push_back(pool[j+1]);
            }
            bool did = false;
            if(i<n){
                did = true;
                q.push_back(i++);
            }
            int r = use(q);
            if(did){
                if(r%2 == 0){
                    occ[me].push_back(q.back());
                } else {
                    occ[!me].push_back(q.back());
                    --r;
                }
            }
            r /= 2;
            if(me == 0) r = U-r;
            ans += r;
        }
        ans += occ[0].size();
    }
    return ans;

}

• Subtask 1: 92.623 / 100