Submission #1230008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230008		a4n_	Counting Mushrooms (IOI20_mushrooms)	C++20	80.14 / 100	3 ms	436 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, s[N];
vector<int> vec[2];

int count_mushrooms(int _n)  {
    n = _n;

    if(n <= 4) {
        int ans = 1;
        for(int i=1; i<n; i++) {
            ans += (use_machine({0, i}) == 0);
        }
        return ans;
    }
    
    s[1] = (use_machine({0, 1}) == 1);
    s[2] = (use_machine({0, 2}) == 1);

    vec[s[0]].pb(0);
    vec[s[1]].pb(1);
    vec[s[2]].pb(2);

    int ptr = 3;
    while(ptr <= n-2 && max(size(vec[0]), size(vec[1])) < 130) {
        int tp = (size(vec[0]) >= size(vec[1]) ? 0 : 1);
        int res = use_machine({vec[tp][0], ptr, vec[tp][1], ptr + 1});
        
        if(res % 2 == 1) {
            s[ptr + 1] = 1 - tp;
        } else s[ptr + 1] = tp;

        if(res >= 2) s[ptr] = 1 - tp;
        else s[ptr] = tp;
        
        vec[s[ptr]].pb(ptr);
        vec[s[ptr+1]].pb(ptr+1);
        ptr += 2;
    }

    int ans = size(vec[0]);
    while(ptr <= n-1) {
        int tp = (size(vec[0]) >= size(vec[1]) ? 0 : 1);
        
        vector<int> tmp;

        int pt2 = 0;
        while(pt2 < size(vec[tp]) && ptr < n) {
            tmp.pb(ptr); ptr ++;
            tmp.pb(vec[tp][pt2]); pt2 ++;
        }

        int res = use_machine(tmp);
        res = (res + 1) / 2;
        if(tp == 0) res = size(tmp) / 2 - res;
        
        ans += res;
    }

    return ans;
}

// int use_machine(std::vector<int> x);

• Subtask 1: 80.1418 / 100