Submission #409333

#	Time	Username	Problem	Language	Result	Execution time	Memory
409333		Carmel_Ab1	Counting Mushrooms (IOI20_mushrooms)	C++17	32.29 / 100	18 ms	704 KiB

mushrooms

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

//#include "stub.cpp"

using namespace std;

#define pb push_back
typedef vector<int> vi;
typedef long long ll;

int count_mushrooms(int n) {
    int ans=1;

    vi o,z,a(n,-1);
    a[0]=0;
    z.pb(0);

    if(n<=226){
        for(int i=1; i<n; i++)
            ans+=1- use_machine({0,i});
        return ans;
    }
    const int k=max(2ll,ll(sqrt(n)));

    int first=1;
    for(int i=1; o.size()<k && z.size()<k;first++, i++){
        if(use_machine({0,i}))
            o.pb(i),a[i]=1;
        else
            ans++,z.pb(i),a[i]=0;
    }
    vi left;
    for(int i=first; i<n;i++)
        left.pb(i);

    if(o.size()>z.size()){
        for(int i=k,j=0; i<n;j=0, i++){
            vi cur;
            while(left.size() && cur.size()+3<=n && cur.size()+2<=o.size()){
                cur.pb(o[j]);
                cur.pb(left.back());
                left.pop_back();
                cur.pb(o[j+1]);
                j+=2;
            }
            if(cur.size()>=2)
                ans+= use_machine(cur)/2;
        }
    }
    else{
        for(int i=k,j=0; i<n;j=0, i++){
            int in=0;
            vi cur;
            while(left.size() && cur.size()+3<=n && cur.size()+2<=z.size()){
                cur.pb(z[j]);
                cur.pb(left.back());
                left.pop_back();
                cur.pb(z[j+1]);
                j+=2;
                in++;
            }

            if(cur.size()>=2)
                ans+= in-use_machine(cur)/2;
        }
    }
    while(left.size()){
        ans+= use_machine({0,left.back()});
        left.pop_back();
    }
    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:27:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   27 |     for(int i=1; o.size()<k && z.size()<k;first++, i++){
      |                  ~~~~~~~~^~
mushrooms.cpp:27:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   27 |     for(int i=1; o.size()<k && z.size()<k;first++, i++){
      |                                ~~~~~~~~^~
mushrooms.cpp:40:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             while(left.size() && cur.size()+3<=n && cur.size()+2<=o.size()){
      |                                  ~~~~~~~~~~~~^~~
mushrooms.cpp:55:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |             while(left.size() && cur.size()+3<=n && cur.size()+2<=z.size()){
      |                                  ~~~~~~~~~~~~^~~

• Subtask 1: 32.2857 / 100