Submission #871318

#	Time	Username	Problem	Language	Result	Execution time	Memory
871318		andrei_boaca	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	5 ms	964 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int lim=142;
int val[20005];
int count_mushrooms(int n)
{
    vector<int> ord;
    int nra=1,nrb=0;
    val[0]=1;
    vector<int> v={0,1};
    int x=use_machine(v);
    if(x==1)
    {
        val[1]=2;
        nrb++;
    }
    else
    {
        val[1]=1;
        nra++;
    }
    if(n==2)
        return nra;
    v={0,2};
    x=use_machine(v);
    if(x==1)
    {
        val[2]=2;
        nrb++;
    }
    else
    {
        val[2]=1;
        nra++;
    }
    x=-1;
    int y=-1;
    for(int i=1;i<=2;i++)
        if(val[i]==1)
        {
            x=0;
            y=i;
            break;
        }
    if(x==-1)
    {
        x=1;
        y=2;
    }
    int poz=3;
    for(int i=poz;i<n;i++)
        ord.push_back(i);
    shuffle(ord.begin(),ord.end(),rng);
    poz=0;
    while(max(nra,nrb)<lim&&poz<ord.size())
    {
        if(poz+1<ord.size())
        {
            int ans=use_machine({x,ord[poz],y,ord[poz+1]});
            if(x==0)
            {
                if(ans==0)
                {
                    nra+=2;
                    val[ord[poz]]=1;
                    val[ord[poz+1]]=1;
                }
                if(ans==1)
                {
                    nra++;
                    nrb++;
                    val[ord[poz]]=1;
                    val[ord[poz+1]]=2;
                }
                if(ans==2)
                {
                    nra++;
                    nrb++;
                    val[ord[poz]]=2;
                    val[ord[poz+1]]=1;
                }
                if(ans==3)
                {
                    nrb+=2;
                    val[ord[poz]]=2;
                    val[ord[poz+1]]=2;
                }
            }
            else
            {
                if(ans==3)
                {
                    nra+=2;
                    val[ord[poz]]=1;
                    val[ord[poz+1]]=1;
                }
                if(ans==2)
                {
                    nra++;
                    nrb++;
                    val[ord[poz]]=1;
                    val[ord[poz+1]]=2;
                }
                if(ans==1)
                {
                    nra++;
                    nrb++;
                    val[ord[poz]]=2;
                    val[ord[poz+1]]=1;
                }
                if(ans==0)
                {
                    nrb+=2;
                    val[ord[poz]]=2;
                    val[ord[poz+1]]=2;
                }
            }
            poz+=2;
        }
        else
        {
            v={0,ord[poz]};
            int ans=use_machine(v);
            if(ans==1)
            {
                val[ord[poz]]=2;
                nrb++;
            }
            else
            {
                val[ord[poz]]=1;
                nra++;
            }
            return nra;
        }
    }
    vector<int> nums;
    bool isA=0;
    if(nra>=lim)
    {
        isA=1;
        for(int i=0;i<n&&nums.size()<lim;i++)
            if(val[i]==1)
                nums.push_back(i);
    }
    else
    {
        isA=0;
        for(int i=0;i<n&&nums.size()<lim;i++)
            if(val[i]==2)
                nums.push_back(i);
    }
    while(poz<ord.size())
    {
        int cnt=min((int)ord.size()-poz,lim);
        v.clear();
        for(int i=0;i<cnt;i++)
        {
            v.push_back(nums[i]);
            v.push_back(ord[poz+i]);
        }
        int ans=use_machine(v);
        int inegal=ans/2+ans%2;
        int egal=cnt-inegal;
        if(isA)
        {
            nra+=egal;
            nrb+=inegal;
        }
        else
        {
            nra+=inegal;
            nrb+=egal;
        }
        poz+=cnt;
    }
    return nra;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:58:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while(max(nra,nrb)<lim&&poz<ord.size())
      |                             ~~~^~~~~~~~~~~
mushrooms.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if(poz+1<ord.size())
      |            ~~~~~^~~~~~~~~~~
mushrooms.cpp:145:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |         for(int i=0;i<n&&nums.size()<lim;i++)
      |                          ~~~~~~~~~~~^~~~
mushrooms.cpp:152:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  152 |         for(int i=0;i<n&&nums.size()<lim;i++)
      |                          ~~~~~~~~~~~^~~~
mushrooms.cpp:156:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     while(poz<ord.size())
      |           ~~~^~~~~~~~~~~

• Subtask 1: 80.427 / 100