Submission #1029515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029515		irmuun	Counting Mushrooms (IOI20_mushrooms)	C++17	80.14 / 100	6 ms	600 KiB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
int count_mushrooms(int n){
    if(n<=200){
        int ans=1;
        for(int i=1;i<n;i++){
            int d=use_machine({0,i});
            if(d==0){
                ans++;
            }
        }
        return ans;
    }
    int ans=0;
    vector<int>a,b;
    a.pb(0);
    for(int i=1;i<3;i++){
        int d=use_machine({0,i});
        if(d==0){
            a.pb(i);
        }
        else{
            b.pb(i);
        }
    }
    if(a.size()>=2){
        for(int i=3;i<280;i+=2){
            int d=use_machine({a[0],i,a[1],i+1});
            if(d<=1) a.pb(i);
            else b.pb(i);
            if(d%2==0) a.pb(i+1);
            else b.pb(i+1);
        }
    }
    else{
        for(int i=3;i<280;i+=2){
            int d=use_machine({b[0],i,b[1],i+1});
            if(d<=1) b.pb(i);
            else a.pb(i);
            if(d%2==0) b.pb(i+1);
            else a.pb(i+1);
        }
    }
    ans=a.size();
    if(b.size()>a.size()){
        int len=b.size();
        len--;
        for(int i=281;i<n;i+=len){
            int r=min(i+len-1,n-1);
            int cur=1;
            vector<int>v;
            v.pb(b[0]);
            for(int j=i;j<=r;j++){
                v.pb(j);
                v.pb(b[cur]);
                cur++;
            }
            for(int j=cur;j<b.size();j++){
                v.pb(b[j]);
            }
            ans+=use_machine(v)/2;
        }
    }
    else{
        int len=a.size();
        len--;
        for(int i=281;i<n;i+=len){
            int r=min(i+len-1,n-1);
            int cur=1;
            vector<int>v;
            v.pb(a[0]);
            int cnt=0;
            for(int j=i;j<=r;j++){
                v.pb(j);
                cnt++;
                v.pb(a[cur]);
                cur++;
            }
            for(int j=cur;j<a.size();j++){
                v.pb(a[j]);
            }
            ans+=cnt-use_machine(v)/2;
        }
    }
    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:68:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int j=cur;j<b.size();j++){
      |                           ~^~~~~~~~~
mushrooms.cpp:89:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(int j=cur;j<a.size();j++){
      |                           ~^~~~~~~~~

• Subtask 1: 80.1418 / 100