Submission #597682

#	Time	Username	Problem	Language	Result	Execution time	Memory
597682		ogibogi2004	Counting Mushrooms (IOI20_mushrooms)	C++14	75.84 / 100	11 ms	356 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K=100;
int count_mushrooms(int n) {
    vector<int>A,B;
    A.push_back(0);
    int cnta=1;
    int decided=-1;
    for(int i=1;i<n;)
    {
        int last=i;
        if(decided==0)
        {
            vector<int>v;
            for(int j=0;j<A.size()&&j<K&&i+j<n;j++)
            {
                last=i+j;
                if(i+j>=n)break;
                v.push_back(i+j);
                v.push_back(A[j]);
            }
            int f=use_machine(v);
            cnta+=v.size()/2-(f+1)/2;
            if(f%2==0)
            {
                A.push_back(i);
            }
            else
            {
                B.push_back(i);
            }
        }
        else if(decided==1)
        {
            vector<int>v;
            for(int j=0;j<B.size()&&j<K&&i+j<n;j++)
            {
                last=i+j;
                if(i+j>=n)break;
                v.push_back(i+j);
                v.push_back(B[j]);
            }
            int f=use_machine(v);
            cnta+=(f+1)/2;
            if(f%2==0)
            {
                B.push_back(i);
            }
            else
            {
                A.push_back(i);
            }
        }
        else
        {
            if(A.size()>B.size())
            {
                vector<int>v;
                for(int j=0;j<A.size()&&j<K&&i+j<n;j++)
                {
                    last=i+j;
                    if(i+j>=n)break;
                    v.push_back(i+j);
                    v.push_back(A[j]);
                }
                int f=use_machine(v);
                cnta+=v.size()/2-(f+1)/2;
                if(f%2==0)
                {
                    A.push_back(i);
                }
                else
                {
                    B.push_back(i);
                }
            }
            else
            {
                vector<int>v;
                for(int j=0;j<B.size()&&j<K&&i+j<n;j++)
                {
                    last=i+j;
                    if(i+j>=n)break;
                    v.push_back(i+j);
                    v.push_back(B[j]);
                }
                int f=use_machine(v);
                cnta+=(f+1)/2;
                if(f%2==0)
                {
                    B.push_back(i);
                }
                else
                {
                    A.push_back(i);
                }
            }
            if(A.size()==K)decided=0;
            else if(B.size()==K)decided=1;
        }
        //cout<<last<<" "<<cnta<<endl;
        i=last+1;
    }
    return cnta;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:16:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for(int j=0;j<A.size()&&j<K&&i+j<n;j++)
      |                         ~^~~~~~~~~
mushrooms.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int j=0;j<B.size()&&j<K&&i+j<n;j++)
      |                         ~^~~~~~~~~
mushrooms.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 for(int j=0;j<A.size()&&j<K&&i+j<n;j++)
      |                             ~^~~~~~~~~
mushrooms.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for(int j=0;j<B.size()&&j<K&&i+j<n;j++)
      |                             ~^~~~~~~~~

• Subtask 1: 75.8389 / 100