제출 #335398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335398		rocks03	버섯 세기 (IOI20_mushrooms)	C++14	80.71 / 100	12 ms	492 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int use_machine(vector<int> x);

int count_mushrooms(int n){
    vector<int> a, b;
    a.pb(0);
    int ans = 1, i = 1;
    while(1){
        if(i >= n) break;
        if(SZ(a) > SZ(b)){
            vector<int> v;
            int j = i;
            while(j < n && j < i + SZ(a)){
                v.pb(a[j - i]);
                v.pb(j);
                j++;
            }
            int res = use_machine(v);
            ans += SZ(v) / 2 - (res + 1) / 2;
            i = j;
            if(res&1){
                b.pb(i - 1);
            } else{
                a.pb(i - 1);
            }
        } else{
            vector<int> v;    
            int j = i;
            while(j < n && j < i + SZ(b)){
                v.pb(b[j - i]);
                v.pb(j);
                j++;
            }
            int res = use_machine(v);
            ans += (res + 1) / 2;
            i = j;
            if(res&1){
                a.pb(i - 1);
            } else{
                b.pb(i - 1);
            }
        }
    }
	return ans;
}

• Subtask 1: 80.7143 / 100