oj.uz

Submission #1012418

# Submission time Handle Problem Language Result Execution time Memory
1012418 2024-07-02T06:31:54 Z bachhoangxuan Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 5 ms 600 KB 
#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
const int K=100;

int count_mushrooms(int n) {
    if(n<=450){
        int cnt=1;
        for(int i=1;i<n;i+=2){
            vector<int> x={i};
            x.push_back(0);
            if(i+1<n) x.push_back(i+1);
            cnt+=(int)x.size()-1-use_machine(x);
        }
        return cnt;
    }
    int t=0,res=0;
    vector<vector<int>> a(2);
    a[0].push_back(0);
    a[use_machine({0,1})].push_back(1);
    a[use_machine({0,2})].push_back(2);
    auto update = [&](){
        if(sz(a[0])<sz(a[1])){
            swap(a[0],a[1]),t^=1;
            return true;
        }
        return false;
    };
    update();

    int x=use_machine({3,a[0][0],4,a[0][1]});
    a[x&1].push_back(3);
    a[x>>1].push_back(4);
    update();

    for(int i=5;sz(a[0])<K;){
        x=use_machine({i,a[0][0],i+1,a[0][1],i+2,a[0][2]});
        a[x&1].push_back(i);
        if(!(x&2)){
            x>>=2;
            a[x].push_back(i+1);
            a[x].push_back(i+2);
            i+=3;
        }
        else if(sz(a[1])<2){
            x=use_machine({i+1,a[0][0]});
            a[x].push_back(i+1);
            a[x^1].push_back(i+2);
            i+=3;
        }
        else{
            x=use_machine({i+4,a[0][0],i+3,a[0][1],i+2,a[0][2],a[1][0],i+1,a[1][1]})-1;
            a[x&1].push_back(i+4);x>>=1;
            a[x&1].push_back(i+3);x>>=1;
            a[x].push_back(i+2);
            a[x^1].push_back(i+1);
            i+=5;
        }
        update();
    }
    res=sz(a[1]);
    for(int i=sz(a[0])+sz(a[1]);i<n;){
        int r=min(i+sz(a[0]),n);
        vector<int> m;
        for(int j=i;j<r;j++){
            m.push_back(j);
            m.push_back(a[0][j-i]);
        }
        x=use_machine(m);
        res+=(x+1)/2;
        a[x&1].push_back(i);
        if(update()) res=r-res;
        i=r;
    }
    return (t?res:n-res);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 3 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 3 ms 448 KB Output is correct
14 Correct 2 ms 344 KB Output is correct
15 Correct 5 ms 600 KB Output is correct
16 Correct 3 ms 344 KB Output is correct
17 Correct 3 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 3 ms 344 KB Output is correct
20 Correct 3 ms 344 KB Output is correct
21 Correct 3 ms 344 KB Output is correct
22 Correct 3 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 3 ms 452 KB Output is correct
25 Correct 3 ms 344 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Correct 3 ms 432 KB Output is correct
28 Correct 3 ms 344 KB Output is correct
29 Correct 5 ms 600 KB Output is correct
30 Correct 4 ms 340 KB Output is correct
31 Correct 5 ms 344 KB Output is correct
32 Correct 5 ms 344 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 2 ms 344 KB Output is correct
35 Correct 3 ms 600 KB Output is correct
36 Correct 3 ms 344 KB Output is correct
37 Correct 3 ms 344 KB Output is correct
38 Correct 5 ms 344 KB Output is correct
39 Correct 3 ms 444 KB Output is correct
40 Correct 3 ms 344 KB Output is correct
41 Correct 3 ms 344 KB Output is correct
42 Correct 3 ms 344 KB Output is correct
43 Correct 4 ms 600 KB Output is correct
44 Correct 5 ms 344 KB Output is correct
45 Correct 3 ms 344 KB Output is correct
46 Correct 5 ms 344 KB Output is correct
47 Correct 3 ms 344 KB Output is correct
48 Correct 3 ms 344 KB Output is correct
49 Correct 3 ms 344 KB Output is correct
50 Correct 3 ms 344 KB Output is correct
51 Correct 3 ms 460 KB Output is correct
52 Correct 3 ms 344 KB Output is correct
53 Correct 3 ms 344 KB Output is correct
54 Correct 5 ms 344 KB Output is correct
55 Correct 5 ms 344 KB Output is correct
56 Correct 4 ms 596 KB Output is correct
57 Correct 4 ms 344 KB Output is correct
58 Correct 3 ms 600 KB Output is correct
59 Correct 3 ms 456 KB Output is correct
60 Correct 4 ms 344 KB Output is correct
61 Correct 3 ms 344 KB Output is 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 0 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 0 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