Submission #608406

#	Time	Username	Problem	Language	Result	Execution time	Memory
608406		krit3379	Counting Mushrooms (IOI20_mushrooms)	C++17	75.59 / 100	21 ms	336 KiB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

int ca,cb,now;
vector<int> a,b;

void ch(int x){
    if(use_machine({0,x}))b.push_back(x);
    else a.push_back(x);
}

int count_mushrooms(int n){
    int i,j,val;
    a.push_back(0);
    now=1;
    if(n<226){
        for(i=1;i<n;i++)ch(i);
        return a.size();
    }
    ch(now++);
    if(a.size()<2)ch(now++);
    if(a.size()==2){
        while(a.size()<100&&b.size()<100){
            val=use_machine({a[0],now,a[1],now+1});
            if(val==0)a.push_back(now),a.push_back(now+1);
            else if(val==1)a.push_back(now),b.push_back(now+1);
            else if(val==2)b.push_back(now),a.push_back(now+1);
            else if(val==3)b.push_back(now),b.push_back(now+1);
            now+=2;
        }
    }
    else{
        while(a.size()<100&&b.size()<100){
            val=use_machine({b[0],now,b[1],now+1});
            if(val==0)b.push_back(now),b.push_back(now+1);
            else if(val==1)b.push_back(now),a.push_back(now+1);
            else if(val==2)a.push_back(now),b.push_back(now+1);
            else if(val==3)a.push_back(now),a.push_back(now+1);
            now+=2;
        }
    }
    if(a.size()>=100){
        vector<int> v;
        while(now+a.size()<=n){
            for(auto x:a)v.push_back(x),v.push_back(now++);
            cb+=(use_machine(v)+1)/2;
            v.clear();
        }
        i=0;
        while(now<n){
            v.push_back(a[i++]);
            v.push_back(now++);
        }
        if(!v.empty())cb+=(use_machine(v)+1)/2;
        return n-b.size()-cb;
    }
    else{
        vector<int> v;
        while(now+b.size()<=n){
            for(auto x:b)v.push_back(x),v.push_back(now++);
            ca+=(use_machine(v)+1)/2;
            v.clear();
        }
        i=0;
        while(now<n){
            v.push_back(b[i++]);
            v.push_back(now++);
        }
        if(!v.empty())ca+=(use_machine(v)+1)/2;
        return a.size()+ca;
    }
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         while(now+a.size()<=n){
      |               ~~~~~~~~~~~~^~~
mushrooms.cpp:63:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         while(now+b.size()<=n){
      |               ~~~~~~~~~~~~^~~
mushrooms.cpp:17:11: warning: unused variable 'j' [-Wunused-variable]
   17 |     int i,j,val;
      |           ^

• Subtask 1: 75.5853 / 100