제출 #1248571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248571		nikulid	버섯 세기 (IOI20_mushrooms)	C++20	90.40 / 100	3 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
#include <vector>

using namespace std;

bool debug=1;
#define dout if(debug)cout

#define pb push_back
#define mp make_pair

int count_mushrooms(int n) {
        vector<int> m;
        if(n<200){
          int answer=1;
          for(int i=1; i<n; i++){
            m = {0,i};
            answer += 1-use_machine(m);
          }
          return answer;
        }
        m = {0,1};
        int a = use_machine(m);
        m = {0,2};
        int b = use_machine(m);
        pair<int, int> ps;
        bool usingzeros;

        vector<int> zeros={0};
        vector<int> ones;

        if(a){
                // {0,1}
                ones.pb(1);
                if(b){
                        // {0,1,1}
                        ones.pb(2);
                        usingzeros=false;
                        ps={1,2};
                } else{
                        // {0,1,0}
                        zeros.pb(2);
                        usingzeros=true;
                        ps={0,2};
                }
        } else{
                // {0,0}
                zeros.pb(1);
                usingzeros=true;
                ps={0,1};
                if(b){
                        // {0,0,1}
                        ones.pb(2);
                } else{
                        // {0,0,0}
                        zeros.pb(2);
                }
        }

        // now, after 2 queries, we have at least 2 of the same type .
        // we take advatnage hereof with queries of the form {A,x,A,y}.

        int val;

        for(int i=2; i<98; i+=2){
                m={ps.first, i+1, ps.second, i+2};
                val = use_machine(m);
                if(val==0){
                        // {A,a,A,a}
                        if(usingzeros){
                                zeros.pb(i+1);
                                zeros.pb(i+2);
                        } else{
                                ones.pb(i+1);
                                ones.pb(i+2);
                        }
                } else if(val==1){
                        // {A,a,A,b}
                        if(usingzeros){
                                zeros.pb(i+1);
                                ones.pb(i+2);
                        } else{
                                ones.pb(i+1);
                                zeros.pb(i+2);
                        }
                } else if(val==2){
                        // {A,b,A,a}
                        if(usingzeros){
                                ones.pb(i+1);
                                zeros.pb(i+2);
                        } else{
                                zeros.pb(i+1);
                                ones.pb(i+2);
                        }
                } else{
                        // {A,b,A,b}
                        if(usingzeros){
                                ones.pb(i+1);
                                ones.pb(i+2);
                        } else{
                                zeros.pb(i+1);
                                zeros.pb(i+2);
                        }
                }
        }

        int c0 = zeros.size();
        int c1 = ones.size();

        int cur = 99;
        int cycles;
        while(cur < n){
                m.resize(0);
                cycles=0;
                if(zeros.size()>ones.size()){
                        // use A=0
                        for(int i=0; i<zeros.size(); i++){
                                cycles++;
                                m.pb(zeros[i]);
                                m.pb(cur);
                                cur++;
                                if(cur>=n)break;
                        }
                        val = use_machine(m);
                        c1 += (val+1)/2;
                        c0 += cycles-((val+1)/2);
                        if(val%2==0){ // last one is A=0
                                zeros.pb(cur-1);
                        } else ones.pb(cur-1);
                } else{
                        // use A=1
                        for(int i=0; i<ones.size(); i++){
                                cycles++;
                                m.pb(ones[i]);
                                m.pb(cur);
                                cur++;
                                if(cur>=n)break;
                        }
                        val = use_machine(m);
                        c0 += (val+1)/2;
                        c1 += cycles-((val+1)/2);
                        if(val%2==0){ // last one is A=1
                                ones.pb(cur-1);
                        } else zeros.pb(cur-1);
                }
        }
        return c0;
}

• Subtask 1: 90.4 / 100