oj.uz

Submission #364949

# Submission time Handle Problem Language Result Execution time Memory
364949 2021-02-10T14:25:46 Z leinad2 Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 11 ms 548 KB 
#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
    if(n<=200)
    {
        int ans=1;
        for(int i=1;i<n;i++)
        {
            vector<int>v;
            v.push_back(0);v.push_back(i);
            if(use_machine(v)==0)ans++;
        }
        return ans;
    }
    vector<int>v[2];
    v[0].push_back(0);
    vector<int>qr;
    qr.push_back(0);qr.push_back(1);
    v[use_machine(qr)].push_back(1);
    qr.pop_back();qr.push_back(2);
    v[use_machine(qr)].push_back(2);
    int y=0;
    if(v[0].size()<2)y=1;
    qr.clear();
    qr.push_back(v[y][0]);
    qr.push_back(3);
    qr.push_back(v[y][1]);
    qr.push_back(4);
    int ans=use_machine(qr);
    v[(ans/2+y)%2].push_back(3);
    v[(ans+y)%2].push_back(4);
    int x=0;
    if(v[0].size()<3)x=1;
    int bu=45;
    for(int i=1;i<bu;i++)
    {
        vector<int>q;
        q.push_back(v[x][0]);q.push_back(5*i);q.push_back(v[x][1]);q.push_back(5*i+1);q.push_back(v[x][2]);q.push_back(5*i+2);
        int ans=use_machine(q);
        if(ans/2==1)
        {
            v[(ans+x)%2].push_back(5*i+2);
            if(v[1-x].size()<2)
            {
                vector<int>qr;
                qr.push_back(v[x][0]);
                qr.push_back(5*i+3);
                qr.push_back(v[x][1]);
                qr.push_back(5*i+4);
                int ans=use_machine(qr);
                v[(ans/2+x)%2].push_back(5*i+3);
                v[(ans+x)%2].push_back(5*i+4);
                qr.clear();
                qr.push_back(v[x][0]);
                qr.push_back(5*i);
                ans=use_machine(qr);
                v[(ans+x)%2].push_back(5*i);
                v[(ans+x+1)%2].push_back(5*i+1);
            }
            else
            {
                vector<int>qr;
                qr.push_back(v[1-x][0]);
                qr.push_back(5*i);
                qr.push_back(v[1-x][1]);
                qr.push_back(v[x][0]);
                qr.push_back(5*i+1);
                qr.push_back(v[x][1]);
                qr.push_back(5*i+3);
                qr.push_back(v[x][2]);
                qr.push_back(5*i+4);
                int ans=use_machine(qr);
                ans--;
                v[(ans/4+x+1)%2].push_back(5*i);
                v[(ans/4+x)%2].push_back(5*i+1);
                ans%=4;
                v[(ans/2+x)%2].push_back(5*i+3);
                v[(ans+x)%2].push_back(5*i+4);
            }
        }
        else
        {
            v[(ans/4+x)%2].push_back(5*i);
            v[(ans/4+x)%2].push_back(5*i+1);
            v[(ans+x)%2].push_back(5*i+2);
            vector<int>qr;
            qr.push_back(v[x][0]);
            qr.push_back(5*i+3);
            qr.push_back(v[x][1]);
            qr.push_back(5*i+4);
            int ans=use_machine(qr);
            v[(ans/2+x)%2].push_back(5*i+3);
            v[(ans+x)%2].push_back(5*i+4);
        }
    }
    int jump;
    int ret=v[0].size();
    for(int i=5*bu;i<n;i+=jump)
    {
        int k;
        if(v[0].size()>v[1].size())
        {
            k=0;
            jump=v[0].size();
        }
        else
        {
            k=1;
            jump=v[1].size();
        }
        vector<int>quer;
        for(int j=i;j<min(i+jump, n);j++)
        {
            quer.push_back(v[k][j-i]);
            quer.push_back(j);
        }
        int ans=use_machine(quer);
        if(k)ret+=(ans/2+ans%2);
        else ret-=(ans/2+ans%2),ret+=(min(i+jump, n)-i);
        v[(ans%2)^k].push_back(min(i+jump, n)-1);
    }
    return ret;
}

Subtask #1
100.0 / 100.0

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