Submission #661227

#	Time	Username	Problem	Language	Result	Execution time	Memory
661227		perchuts	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	10 ms	340 KiB

mushrooms

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "mushrooms.h"
using namespace std;

template<typename X,typename Y> bool ckmin(X& x,Y y){return (x>y?x=y,1:0);}

using ii = pair<int,int>;

int use_machine(vector<int> x);

int count_mushrooms(int n){
    vector<int>m;
    vector<vector<int>>v(2,vector<int>());

    int k = (n<=500?100:88), x, y, type = 0;
    
    if(n<=226){ 
        int ans = 1;
        for(int i=1;i<n;++i)ans += (1 - use_machine({0,i}));
        return ans;
    }

    v[0].pb(0);

    int r1 = use_machine({0,1}), r2 = use_machine({0,2});

    if(r1)v[1].pb(1);
    else v[0].pb(1);

    if(r2)v[1].pb(2);
    else v[0].pb(2);


    if(!r1)x = 0, y = 1;
    else if(!r2)x = 0, y = 2;    
    else x = 1, y = 2, type = 1;

    for(int i=3;i<2*k-1;i+=2){
        assert(i+1<n);
        int cur = use_machine({i,x,i+1,y});

        if(cur&1)v[type^1].pb(i);
        else v[type].pb(i);

        if(cur>=2)v[type^1].pb(i+1);
        else v[type].pb(i+1);
    }

    //deve dar uns 80 pontos

    int target = (sz(v[0])>=k?0:1), ans = sz(v[0]);

    for(int i=2*k-1;i<n;i+=k){
        
        if(sz(v[target^1])>sz(v[target]))target ^= 1;
        k = sz(v[target]);

        vector<int>ask;
        for(int j=0;j<k&&i+j<n;++j){
            ask.pb(i+j), ask.pb(v[target][j]);
        }

        int cur = use_machine(ask);

        if(cur&1)v[target^1].pb(i);
        else v[target].pb(i);

        if(target==1)ans += (cur+1)/2;
        else ans += min(n-i,k) - (cur+1)/2;
    }

    return ans;
}

• Subtask 1: 92.623 / 100