Submission #365575

#	Time	Username	Problem	Language	Result	Execution time	Memory
365575		qwerasdfzxcl	Counting Mushrooms (IOI20_mushrooms)	C++14	92.62 / 100	11 ms	544 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> m;
vector<int> a, b, val;
/*
int use_machine(vector<int> &v){
    int ret;
    for (int x:v) printf("%d ", x);
    printf("\n");
    scanf("%d", &ret);
    return ret;
}*/

int count_mushrooms(int n){
    if (n<=226){
        m.push_back(0);
        int ret=1;
        for (int i=1;i<n;i++){
            m.push_back(i);
            if (use_machine(m)==0) ret++;
            m.pop_back();
        }
        //printf("%d\n", ret);
        return ret;
    }
    m.push_back(0);
    a.push_back(0);
    int chk=1;
    for (int i=1;i<=2;i++){
        chk++;
        m.push_back(i);
        val.push_back(use_machine(m));
        if (val.back()) b.push_back(i);
        else{
            a.push_back(i);
            break;
        }
        m.pop_back();
    }
    m.clear();
    m.resize(4, 0);
    int cur_state;
    if (a.size()>b.size()){
        cur_state=1;
        m[1]=0; m[3]=a[1];
    }
    else{
        cur_state=2;
        m[1]=b[0]; m[3]=b[1];
    }
    int vall=150;
    for (;(int)a.size()+(int)b.size()<vall;chk += 2){
        m[0]=chk; m[2]=chk+1;
        val.push_back(use_machine(m));
        if (val.back()&1){
            if (cur_state==1) b.push_back(chk);
            else a.push_back(chk);
        }
        else{
            if (cur_state==1) a.push_back(chk);
            else b.push_back(chk);
        }
        if (val.back()&2){
            if (cur_state==1) b.push_back(chk+1);
            else a.push_back(chk+1);
        }
        else{
            if (cur_state==1) a.push_back(chk+1);
            else b.push_back(chk+1);
        }
    }
    m.clear();
    m.resize(2*vall, 0);
    if (a.size()>b.size()){
        cur_state=1;
        for (int i=0;i<vall;i++) m[i*2+1]=a[i];
    }
    else{
        cur_state=2;
        for (int i=0;i<vall;i++) m[i*2+1]=b[i];
    }
    int ans=0, ans2=(int)a.size();
    int sz=max((int)a.size(), (int)b.size());
    while(true){
        if (n-chk<=sz){
            m.clear();
            for (int i=0;i<sz;i++){
                if (chk+i>=n){
                    break;
                }
                m.push_back(chk+i);
                if (cur_state==1)m.push_back(a[i]);
                else m.push_back(b[i]);
            }
            int tmp=use_machine(m);
            tmp++;
            if (cur_state==1) ans += ((int)m.size()/2-tmp/2);
            else ans += tmp/2;
            break;
        }
        m.clear();
        m.resize(2*sz, 0);
        for (int i=0;i<sz;i++){
            if (cur_state==1) m[i*2+1]=a[i];
            else m[i*2+1]=b[i];
        }
        for (int i=0;i<sz;i++){
            m[i*2]=chk+i;
        }
        int tmp=use_machine(m);
        tmp++;
        if (cur_state==1) ans += (sz-tmp/2);
        else ans += tmp/2;
        tmp--;
        if (tmp&1){
            if (cur_state==1) b.push_back(m[0]);
            else a.push_back(m[0]);
        }
        else{
            if (cur_state==2) b.push_back(m[0]);
            else a.push_back(m[0]);
        }
        chk += sz;
        sz=max((int)a.size(), (int)b.size());
        if (a.size()>b.size()) cur_state=1;
        else cur_state=2;
    }
    //printf("%d\n", ans+(int)a.size());
    return ans+ans2;
}
/*
int main(){
    int n;
    scanf("%d", &n);
    printf("%d", count_mushrooms(n));
    return 0;
}*/

• Subtask 1: 92.623 / 100