Submission #423242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
423242	2021-06-10T20:25:52 Z	xyz	Counting Mushrooms (IOI20_mushrooms)	C++17	80.7143 / 100	9 ms	456 KB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef long long ll;

int m = 6;

int count_mushrooms(int n){
    vector<int> A, B;
    A = {0};
    int go = 2 * m + 3;
    for(int i = 1; i < min(n, go); i ++){
        vector<int> ask = {0, i};
        int x = use_machine(ask);
        if(!x)
            A.push_back(i);
        else
            B.push_back(i);
    }
//    for(int x : A)
//        cout << x << " ";
//    cout << endl;
//    for(int x : B)
//        cout << x << " ";
//    cout << endl;
    int result = A.size(), pos = go;
    while(pos < n){
        m = max((int)A.size(), (int)B.size()) - 1;
        if(A.size() >= B.size()){
            vector<int> ask;
            if(pos + m < n)
                ask.push_back(pos + m);
            ask.push_back(A[0]);
            int cur = 1;
            for(int j = pos; j < min(n, pos + m); j ++){
                ask.push_back(j);
                ask.push_back(A[cur]);
                ++ cur;
            }
//            cout << "-query1" << endl;
//            cout << ask.size() << endl;
//            for(int e : ask)
//                cout << e << " ";
//            cout << endl;
            int x = use_machine(ask), y = ask.size();
//            cout << "reply = " << x << endl;
            if(pos + m < n){
                -- y;
                if(x % 2 == 1){
                    B.push_back(pos + m);
                    -- x;
                }else{
                    A.push_back(pos + m);
                    ++ result;
                }
            }
            result += ((y - 1) - x) / 2;
            pos += m + 1;
        }else{
            vector<int> ask;
            if(pos + m < n)
                ask.push_back(pos + m);
            ask.push_back(B[0]);
            int cur = 1;
            for(int j = pos; j < min(n, pos + m); j ++){
                ask.push_back(j);
                ask.push_back(B[cur]);
                ++ cur;
            }
//            cout << "-query2" << endl;
//            cout << ask.size() << endl;
//            for(int e : ask)
//                cout << e << " ";
//            cout << endl;
            int x = use_machine(ask);
//            cout << "reply = " << x << endl;
            if(pos + m < n){
                if(x % 2 == 1){
                    A.push_back(pos + m);
                    ++ result;
                    -- x;
                }else{
                    B.push_back(pos + m);
                }
            }
            result += x / 2;
            pos += m + 1;
        }
    }
    return result;
}

//23
//0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0
//answer : 17

Subtask #1

80.7143 / 100.0

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