Submission #871317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871317	2023-11-10T14:37:34 Z	andrei_boaca	Counting Mushrooms (IOI20_mushrooms)	C++17	80.1418 / 100	6 ms	988 KB

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=150;
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

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.1418 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	388 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	6 ms	720 KB	Output is correct
8	Correct	5 ms	732 KB	Output is correct
9	Correct	4 ms	988 KB	Output is correct
10	Partially correct	4 ms	736 KB	Output is partially correct
11	Partially correct	6 ms	736 KB	Output is partially correct
12	Partially correct	4 ms	728 KB	Output is partially correct
13	Correct	4 ms	732 KB	Output is correct
14	Correct	3 ms	848 KB	Output is correct
15	Partially correct	4 ms	716 KB	Output is partially correct
16	Partially correct	4 ms	984 KB	Output is partially correct
17	Correct	3 ms	460 KB	Output is correct
18	Correct	4 ms	744 KB	Output is correct
19	Partially correct	4 ms	740 KB	Output is partially correct
20	Partially correct	4 ms	676 KB	Output is partially correct
21	Partially correct	4 ms	672 KB	Output is partially correct
22	Partially correct	4 ms	728 KB	Output is partially correct
23	Partially correct	4 ms	740 KB	Output is partially correct
24	Correct	3 ms	716 KB	Output is correct
25	Partially correct	5 ms	740 KB	Output is partially correct
26	Partially correct	4 ms	980 KB	Output is partially correct
27	Partially correct	4 ms	732 KB	Output is partially correct
28	Partially correct	4 ms	732 KB	Output is partially correct
29	Partially correct	5 ms	728 KB	Output is partially correct
30	Partially correct	4 ms	720 KB	Output is partially correct
31	Partially correct	4 ms	732 KB	Output is partially correct
32	Partially correct	5 ms	740 KB	Output is partially correct
33	Partially correct	5 ms	736 KB	Output is partially correct
34	Partially correct	4 ms	732 KB	Output is partially correct
35	Partially correct	4 ms	736 KB	Output is partially correct
36	Partially correct	4 ms	724 KB	Output is partially correct
37	Partially correct	4 ms	736 KB	Output is partially correct
38	Partially correct	4 ms	720 KB	Output is partially correct
39	Partially correct	5 ms	724 KB	Output is partially correct
40	Partially correct	6 ms	728 KB	Output is partially correct
41	Partially correct	4 ms	732 KB	Output is partially correct
42	Partially correct	4 ms	720 KB	Output is partially correct
43	Partially correct	4 ms	720 KB	Output is partially correct
44	Partially correct	5 ms	724 KB	Output is partially correct
45	Partially correct	5 ms	716 KB	Output is partially correct
46	Partially correct	5 ms	724 KB	Output is partially correct
47	Partially correct	5 ms	736 KB	Output is partially correct
48	Partially correct	4 ms	732 KB	Output is partially correct
49	Partially correct	5 ms	736 KB	Output is partially correct
50	Partially correct	4 ms	744 KB	Output is partially correct
51	Partially correct	4 ms	728 KB	Output is partially correct
52	Partially correct	4 ms	740 KB	Output is partially correct
53	Partially correct	6 ms	724 KB	Output is partially correct
54	Partially correct	5 ms	728 KB	Output is partially correct
55	Partially correct	5 ms	968 KB	Output is partially correct
56	Partially correct	4 ms	740 KB	Output is partially correct
57	Partially correct	4 ms	724 KB	Output is partially correct
58	Partially correct	5 ms	964 KB	Output is partially correct
59	Partially correct	4 ms	728 KB	Output is partially correct
60	Partially correct	4 ms	728 KB	Output is partially correct
61	Partially correct	4 ms	728 KB	Output is partially correct
62	Correct	0 ms	344 KB	Output is correct
63	Correct	0 ms	344 KB	Output is correct
64	Correct	0 ms	344 KB	Output is correct
65	Correct	1 ms	344 KB	Output is correct
66	Correct	0 ms	344 KB	Output is correct
67	Correct	0 ms	344 KB	Output is correct
68	Correct	1 ms	344 KB	Output is correct
69	Correct	0 ms	344 KB	Output is correct
70	Correct	0 ms	344 KB	Output is correct
71	Correct	0 ms	344 KB	Output is correct
72	Correct	0 ms	344 KB	Output is correct
73	Correct	0 ms	344 KB	Output is correct
74	Correct	0 ms	344 KB	Output is correct
75	Correct	0 ms	344 KB	Output is correct
76	Correct	0 ms	344 KB	Output is correct
77	Correct	0 ms	344 KB	Output is correct
78	Correct	0 ms	344 KB	Output is correct
79	Correct	0 ms	344 KB	Output is correct
80	Correct	0 ms	344 KB	Output is correct
81	Correct	0 ms	344 KB	Output is correct
82	Correct	0 ms	344 KB	Output is correct
83	Correct	0 ms	344 KB	Output is correct
84	Correct	0 ms	344 KB	Output is correct
85	Correct	0 ms	344 KB	Output is correct
86	Correct	0 ms	344 KB	Output is correct
87	Correct	0 ms	344 KB	Output is correct
88	Correct	0 ms	344 KB	Output is correct
89	Correct	0 ms	344 KB	Output is correct
90	Correct	0 ms	344 KB	Output is correct
91	Correct	0 ms	344 KB	Output is correct