Submission #365717

#	Time	Username	Problem	Language	Result	Execution time	Memory
365717		qwerasdfzxcl	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	9 ms	516 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 cur_state;
bool visited[20020];
/*
int use_machine(vector<int> &v){
    int ret=0;
    for (int x:v) printf("%d ", x);
    printf("\n");
    //scanf("%d", &ret);
    for (int i=1;i<(int)v.size();i++) if ((v[i]>=100 && v[i-1]<100)||(v[i-1]>=100 && v[i]<100)) ret++;
    printf("ret: %d\n", ret);
    return ret;
}*/

void odd(int tmp){
    int abc=2;
    if (tmp&1) abc=1;
    if (cur_state==abc) b.push_back(m[0]);
    else a.push_back(m[0]);
}

void update(){
    if (a.size()>b.size()) cur_state=1;
    else cur_state=2;
}

void init(int val){
    m.clear();
    m.resize(2*val, 0);
    for (int i=0;i<val;i++){
        if (cur_state==1) m[i*2+1]=a[i];
        else m[i*2+1]=b[i];
    }
}

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);
    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];
    }
    for (;(int)a.size()+(int)b.size()<4;chk += 2){
        m[0]=chk; m[2]=chk+1;
        int uiop=use_machine(m);
        odd(uiop);
        int dddd=1;
        if (uiop<2) dddd=2;
        if (cur_state==dddd) b.push_back(m[2]);
        else a.push_back(m[2]);
    }

    int vall=100;
    bool test=0;
    vector<int> t1, t2;
    for (;(int)a.size()<vall && (int)b.size()<vall;){
        if (test){
            update();
            if (max((int)a.size(), (int)b.size())<5){
                init(4);
                m[0]=chk; m[2]=chk+1; m[4]=t1[0]; m[6]=t1[1];
                int tmp=use_machine(m);
                odd(tmp);
                int cc1=1, cc2=1;
                if (tmp>=4) cc1=2;
                if (cur_state==cc1){
                    a.push_back(m[4]);
                    a.push_back(m[6]);
                    b.push_back(t2[0]);
                } 
                else{
                    b.push_back(m[4]);
                    b.push_back(m[6]);
                    a.push_back(t2[0]);
                }
                if (tmp>=4) tmp -= 4;
                if (tmp>=2) cc2=2;
                if (cur_state==cc2) a.push_back(m[2]);
                else b.push_back(m[4]);
                chk += 2;
                test=0;
                continue;
            }
            init(5);
            m[0]=chk; m[2]=chk+1; m[4]=chk+2; m[6]=t1[0]; m[8]=t1[1];
            int tmp=use_machine(m);
            odd(tmp);
            if (tmp==4 || tmp==5){
                m[0]=chk+3; m[2]=chk+4; m[4]=t2[0]; m[6]=chk+1; m[8]=chk+2;
                tmp=use_machine(m);
                odd(tmp);
                int tval=1;
                if (tmp<6) tval=2;
                if (cur_state==tval){
                    b.push_back(t2[0]); b.push_back(chk+1); b.push_back(chk+2); a.push_back(t1[0]); a.push_back(t1[1]);
                }
                else{
                    a.push_back(t2[0]); a.push_back(chk+1); a.push_back(chk+2); b.push_back(t1[0]); b.push_back(t1[1]);
                }
                if (tmp>=6) tmp -= 6;
                tval=1;
                if (tmp==2 || tmp == 3) tval=2;
                if (cur_state==tval) a.push_back(m[2]);
                else b.push_back(m[2]);
                chk += 5;
                test=0;
                continue;
            }
            int asdf=1;
            if (tmp>=4) asdf=2;
            if (cur_state==asdf){
                a.push_back(t1[0]); a.push_back(t1[1]); b.push_back(t2[0]);
            }
            else{
                b.push_back(t1[0]); b.push_back(t1[1]); a.push_back(t2[0]);
            }
            if (tmp>=4) tmp -= 4;
            asdf=1;
            if (tmp<=1) asdf=2;
            if (tmp<=1 || tmp>=4){
                if (cur_state==asdf){
                    b.push_back(m[2]); b.push_back(m[4]);
                }
                else{
                    a.push_back(m[2]); a.push_back(m[4]);
                }
                chk += 3;
                test=0;
                continue;
            }
            t1.clear();
            t2.clear();
            init(3);
            m[0]=chk+3; m[2]=chk+4; m[4]=chk+1;
            tmp=use_machine(m);
            odd(tmp);
            if (tmp==2 || tmp==3){
                t1.push_back(chk+2); t1.push_back(chk+4); t2.push_back(chk+1);
                test=1;
                chk += 5;
                continue;
            }
            asdf=2;
            if (tmp<=1) asdf=1;
            if (cur_state==asdf){
                a.push_back(m[2]); a.push_back(m[4]); b.push_back(chk+2);
            }
            else{
                b.push_back(m[2]); b.push_back(m[4]); a.push_back(chk+2);
            }
            chk += 5;
            test=0;
            continue;
        }
        update();
        init(3);
        m[0]=chk; m[2]=chk+1; m[4]=chk+2;
        int tmp=use_machine(m);
        odd(tmp);
        t1.clear();
        t2.clear();
        if (tmp==2 || tmp==3){
            m[0]=chk+3; m[2]=chk+4; m[4]=chk+1;
            tmp=use_machine(m);
            odd(tmp);
            if (tmp==2 || tmp == 3){
                t1.push_back(chk+2); t1.push_back(chk+4); t2.push_back(chk+1);
                chk += 5;
                test=1;
                continue;
            }
            int qwer=2;
            if (tmp<=1) qwer=1;
            if (cur_state==qwer){
                a.push_back(m[2]); a.push_back(m[4]); b.push_back(chk+2);
            }
            else{
                b.push_back(m[2]); b.push_back(m[4]); a.push_back(chk+2);
            }
            chk += 5;
            test=0;
            continue;
        }
        int zxcv=1;
        if (tmp<=1) zxcv=2;
        if (cur_state==zxcv){
            b.push_back(m[2]); b.push_back(m[4]);
        }
        else{
            a.push_back(m[2]); a.push_back(m[4]);
        }
        chk += 3;
        test=0;
        continue;
    }//end
    if(test){
        update();
        init(4);
        m[0]=chk; m[2]=chk+1; m[4]=t1[0]; m[6]=t1[1];
        int tmp3=use_machine(m);
        odd(tmp3);
        int ch1=1, ch2=1;
        if (tmp3>=4) ch1=2;
        if (cur_state==ch1){
            a.push_back(t1[0]);
            a.push_back(t1[1]);
            b.push_back(t2[0]);
        }
        else{
            b.push_back(t1[0]);
            b.push_back(t1[1]);
            a.push_back(t2[0]);
        }
        if (tmp3>=4) tmp3 -= 4;
        if (tmp3>=2) ch2=2;
        if (cur_state==ch2) a.push_back(m[2]);
        else b.push_back(m[2]);
    }

    chk=0;
    for (int x:a) visited[x]=1;
    for (int x:b) visited[x]=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){
        bool test2=1;
        int c2=0;
        for (int i=0;i<n-chk;i++){
            if (!visited[chk+i]) c2++;
            if (c2==sz){
                test2=0;
                break;
            }
        }
        if (test2){
            m.clear();
            for (int i=0;i<sz;i++){
                if (chk+i>=n){
                    break;
                }
                while(visited[chk+i]) chk++;
                m.push_back(chk+i);
                if (cur_state==1)m.push_back(a[i]);
                else m.push_back(b[i]);
            }
          	if ((int)m.size()==0) break;
            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++){
            while(visited[chk+i]) chk++;
            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: 100 / 100