oj.uz

Submission #346215

# Submission time Handle Problem Language Result Execution time Memory
346215 2021-01-09T07:31:09 Z poom2904 Counting Mushrooms (IOI20_mushrooms) C++14
100 / 100
 10 ms 512 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int cnt_A = 1,cnt_B = 0;
vector<int> A = {0},B;
int i=1;
const int cri=100;//if cnt_A or cnt_B >cri, do func2
void func1()
{
    while(max(cnt_A,cnt_B)<2)
    {
        vector<int> vec = {0,i};
        if(use_machine(vec))
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        i++;
    }
    while((min(cnt_A,cnt_B)<2 || max(cnt_A,cnt_B)<3) && max(cnt_A,cnt_B)<cri)
    {
        bool is_swapped = false;
        if(cnt_A<cnt_B)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        vector<int> vec = {i,A[0],i+1,A[1]};
        int res = use_machine(vec);
        if(res==0)
        {
            cnt_A+=2;
            A.push_back(i);
            A.push_back(i+1);
        }
        else if(res==1)
        {
            cnt_A++;
            cnt_B++;
            A.push_back(i+1);
            B.push_back(i);
        }
        else if(res==2)
        {
            cnt_A++;
            cnt_B++;
            A.push_back(i);
            B.push_back(i+1);
        }
        else
        {
            cnt_B+=2;
            B.push_back(i);
            B.push_back(i+1);
        }
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
        i+=2;
    }
    while(max(cnt_A,cnt_B)<cri)
    {
        bool is_swapped = false;
        if(cnt_A<cnt_B)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        vector<int> vec = {i,A[0],i+1,A[1],i+2,A[2]};
        int res = use_machine(vec);
        if(res&1)
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        if(res-(res&1)==0)
        {
            A.push_back(i+1);
            A.push_back(i+2);
            cnt_A+=2;
            i+=3;
        }
        else if(res-(res&1)==4)
        {
            B.push_back(i+1);
            B.push_back(i+2);
            cnt_B+=2;
            i+=3;
        }
        else
        {
            i++;
            vec = {B[0],i,B[1],A[0],i+1,A[1],i+2,A[2],i+3};
            res = use_machine(vec);
            if(res>4)
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i);
                B.push_back(i+1);
            }
            else
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i+1);
                B.push_back(i);
            }
            if(res%4==1)
            {
                cnt_A+=2;
                A.push_back(i+2);
                A.push_back(i+3);
            }
            else if(res%4==2)
            {
                cnt_A++;
                cnt_B++;
                A.push_back(i+2);
                B.push_back(i+3);
            }
            else if(res%4==3)
            {
                cnt_A++;
                cnt_B++;
                B.push_back(i+2);
                A.push_back(i+3);
            }
            else
            {
                cnt_B+=2;
                B.push_back(i+2);
                B.push_back(i+3);
            }
            i+=4;
        }
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
    }
}
void func2(int n)
{
    while(i<n)
    {
        bool is_swapped = false;
        if(A.size()<B.size())
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
            is_swapped = true;
        }
        int minn = min(int(A.size()),n-i);
        vector<int> vec(minn*2);
        for(int j=0;j<minn;j++)
        {
            vec[j*2] = i+j;
            vec[j*2+1] = A[j];
        }
        int res = use_machine(vec);
        if(res&1)
        {
            cnt_B++;
            B.push_back(i);
        }
        else
        {
            cnt_A++;
            A.push_back(i);
        }
        cnt_A += minn-1-res/2;
        cnt_B += res/2;
        if(is_swapped)
        {
            swap(cnt_A,cnt_B);
            swap(A,B);
        }
        i+=minn;
    }
}
int count_mushrooms(int n) {
    if(n<=227)
    {
        while(i<n)
        {
            vector<int> vec = {0,i};
            if(use_machine(vec))cnt_B++;
            else cnt_A++;
            i++;
        }
        return cnt_A;
    }
	func1();
    func2(n);
	return cnt_A;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 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 7 ms 364 KB Output is correct
8 Correct 9 ms 364 KB Output is correct
9 Correct 7 ms 364 KB Output is correct
10 Correct 8 ms 364 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 7 ms 364 KB Output is correct
14 Correct 4 ms 364 KB Output is correct
15 Correct 7 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 384 KB Output is correct
19 Correct 7 ms 364 KB Output is correct
20 Correct 7 ms 364 KB Output is correct
21 Correct 9 ms 364 KB Output is correct
22 Correct 8 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 7 ms 364 KB Output is correct
27 Correct 7 ms 364 KB Output is correct
28 Correct 7 ms 364 KB Output is correct
29 Correct 7 ms 364 KB Output is correct
30 Correct 6 ms 416 KB Output is correct
31 Correct 7 ms 364 KB Output is correct
32 Correct 6 ms 416 KB Output is correct
33 Correct 8 ms 364 KB Output is correct
34 Correct 9 ms 364 KB Output is correct
35 Correct 8 ms 364 KB Output is correct
36 Correct 7 ms 364 KB Output is correct
37 Correct 8 ms 364 KB Output is correct
38 Correct 8 ms 364 KB Output is correct
39 Correct 7 ms 364 KB Output is correct
40 Correct 9 ms 364 KB Output is correct
41 Correct 6 ms 416 KB Output is correct
42 Correct 9 ms 364 KB Output is correct
43 Correct 10 ms 364 KB Output is correct
44 Correct 8 ms 492 KB Output is correct
45 Correct 9 ms 364 KB Output is correct
46 Correct 9 ms 364 KB Output is correct
47 Correct 10 ms 364 KB Output is correct
48 Correct 8 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 6 ms 416 KB Output is correct
52 Correct 10 ms 364 KB Output is correct
53 Correct 8 ms 364 KB Output is correct
54 Correct 8 ms 364 KB Output is correct
55 Correct 8 ms 364 KB Output is correct
56 Correct 8 ms 364 KB Output is correct
57 Correct 9 ms 364 KB Output is correct
58 Correct 8 ms 364 KB Output is correct
59 Correct 7 ms 364 KB Output is correct
60 Correct 7 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 1 ms 364 KB Output is correct
64 Correct 1 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 384 KB Output is correct
68 Correct 1 ms 364 KB Output is correct
69 Correct 1 ms 364 KB Output is correct
70 Correct 1 ms 364 KB Output is correct
71 Correct 1 ms 364 KB Output is correct
72 Correct 0 ms 364 KB Output is correct
73 Correct 0 ms 364 KB Output is correct
74 Correct 1 ms 364 KB Output is correct
75 Correct 0 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 1 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 1 ms 364 KB Output is correct
83 Correct 1 ms 364 KB Output is correct
84 Correct 1 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 1 ms 364 KB Output is correct
88 Correct 0 ms 364 KB Output is correct
89 Correct 1 ms 364 KB Output is correct
90 Correct 0 ms 364 KB Output is correct
91 Correct 1 ms 364 KB Output is correct