Submission #413142

#	Time	Username	Problem	Language	Result	Execution time	Memory
413142		BJoozz	Counting Mushrooms (IOI20_mushrooms)	C++14	92.24 / 100	12 ms	528 KiB

mushrooms

#include "mushrooms.h"
#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
///shuffle(a.begin(), a.end(), rng)
//#define int long long
const int MAX=20000+4,inf=1e9,M2=5e5+3,K=90;
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
bool cmax(int &a,int b){
    if(b>a){a=b;return 1;} else return 0;
}
typedef pair < int, int > ii;
int a[MAX];
///g++ mushrooms.cpp stub.cpp -std=c++14 -O2
int count_mushrooms(int n) {
    vector<int> vec,v0,v1;
    for(int i=0;i<n;i++) a[i]=i;
    shuffle(a+1,a+n,rng);
	v0.pb(0);
	int cn=0,ans=1;
	if(n>2000){
        vec.pb(0);
        vec.pb(a[++cn]);
        int x=use_machine(vec);
        if(x&1) v1.pb(a[cn]);
        else {v0.pb(a[cn]);ans++;}
        if(v0.size()==1){
            vec.clear();
            vec.pb(0);
            vec.pb(a[++cn]);
            int x=use_machine(vec);
            if(x&1) v1.pb(a[cn]);
            else {v0.pb(a[cn]);ans++;}
        }
        vec.clear();
        if(v0.size()==2){
            for(int i=0;i<K;i++){
                vec.clear();
                vec.pb(v0[0]);
                vec.pb(a[++cn]);
                vec.pb(v0.back());
                vec.pb(a[++cn]);
                int x=use_machine(vec);
                if(x&1)v1.pb(a[cn]);
                else {v0.pb(a[cn]);ans++;}
                if(x&2)v1.pb(a[cn-1]);
                else {v0.pb(a[cn-1]);ans++;}
            }

        }
        else{
            for(int i=0;i<K;i++){
                vec.clear();
                vec.pb(v1[0]);
                vec.pb(a[++cn]);
                vec.pb(v1.back());
                vec.pb(a[++cn]);
                int x=use_machine(vec);
                if(x&1){v0.pb(a[cn]);ans++;}
                else v1.pb(a[cn]);
                if(x&2){v0.pb(a[cn-1]);ans++;}
                else v1.pb(a[cn-1]);
            }
        }
	}


    while(cn!=n-1){
        vec.clear();
        int dem=0;
        if(v0.size()>v1.size()){
            for(int u:v0)if(cn<n-1){
                vec.pb(u);
                vec.pb(a[++cn]);dem++;
            }
            int x=use_machine(vec);
            ans+=(dem-1-x/2);
            if(x&1)v1.pb(a[cn]);
            else {
                v0.pb(a[cn]);
                ans++;
            }
        }
        else{
            /*for(int u:v0){
                vec.pb(u);
                if(cn<n-1 && u!=v0.back())vec.pb(++cn);
            }*/
            for(int u:v1)if(cn<n-1){
                vec.pb(u);
                vec.pb(a[++cn]);dem++;
            }
            int x=use_machine(vec);
            ans+=x/2;
            if(x&1){
                v0.pb(a[cn]);ans++;
            }
            else v1.pb(a[cn]);

        }
    }
    return ans;
}

• Subtask 1: 92.2449 / 100