Submission #365628

#	Time	Username	Problem	Language	Result	Execution time	Memory
365628		qwerasdfzxcl	Counting Mushrooms (IOI20_mushrooms)	C++14	91.87 / 100	18 ms	512 KiB

mushrooms

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

using namespace std;
typedef long long ll;
vector<int> m;
vector<int> a, b, val;
bool visit[20020];
/*
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<=4;i++){
        chk++;
        m.push_back(i);
        val.push_back(use_machine(m));
        if (val.back()) b.push_back(i);
        else{
            a.push_back(i);
        }
        m.pop_back();
    }
    m.clear();
    m.resize(6, 0);
    int cur_state;
    if (a.size()>b.size()){
        cur_state=1;
        m[1]=0; m[3]=a[1]; m[5]=a[2];
    }
    else{
        cur_state=2;
        m[1]=b[0]; m[3]=b[1]; m[5]=b[2];
    }
    int vall=80;
    //if (n<600) vall=50;
    bool test=0;
    int idx1, idx2, prev=chk;
    for (;(int)a.size()<vall && (int)b.size()<vall;){
        while(visit[chk]) chk++;
        m[0]=chk; m[2]=rand()%n; m[4]=rand()%n;
        if (test) m[0]=prev;
        while(visit[m[2]]){
            m[2]=rand()%n;
        }
        visit[m[2]]=1;
        while(visit[m[4]]) m[4]=rand()%n;
        visit[m[4]]=1;
        prev=m[4];
        visit[m[0]]=1;
        val.push_back(use_machine(m));
        if (test){
            if (val.back()&1 && cur_state==2) swap(a[idx1], b[idx2]);
            else if (val.back()%2==0 && cur_state==1) swap(a[idx1], b[idx2]);
        }
        else{
            if (val.back()&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]);
            }
        }
        if (val.back()/2==2){
            test=0;
            if (cur_state==1){
                b.push_back(m[2]);
                b.push_back(m[4]);
            }
            else{
                a.push_back(m[2]);
                a.push_back(m[4]);
            }
        }
        else if (val.back()/2==1){
            test=1;
            a.push_back(m[2]);
            b.push_back(m[4]);
            idx1=(int)a.size()-1;
            idx2=(int)b.size()-1;
        }
        else{
            test=0;
            if (cur_state==2){
                b.push_back(m[2]);
                b.push_back(m[4]);
            }
            else{
                a.push_back(m[2]);
                a.push_back(m[4]);
            }
        }
    }
    if (test){
        m.clear();
        m.push_back(prev);
        m.push_back(0);
        int tmp=use_machine(m);
        if (tmp==0) swap(a[idx1], b[idx2]);
    }
    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 (!visit[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(chk+i<n && visit[chk+i]) chk++;
                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++){
            while(visit[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;
}*/

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:73:75: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             else if (val.back()%2==0 && cur_state==1) swap(a[idx1], b[idx2]);
      |                                                                           ^
mushrooms.cpp:73:66: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             else if (val.back()%2==0 && cur_state==1) swap(a[idx1], b[idx2]);
      |                                                                  ^

• Subtask 1: 91.8699 / 100