Submission #413086

#	Time	Username	Problem	Language	Result	Execution time	Memory
413086		BJoozz	Counting Mushrooms (IOI20_mushrooms)	C++14	80.71 / 100	13 ms	456 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=1e6+4,inf=1e9,M2=5e5+3;
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;
    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: 80.7143 / 100