답안 #522990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522990	2022-02-06T18:13:31 Z	dxz05	버섯 세기 (IOI20_mushrooms)	C++14	92.623 / 100	10 ms	460 KB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

#include <random>

using namespace std;

int count_mushrooms(int n) {
    if (n <= 227){
        int res = 1;
        for (int i = 1; i < n; i++){
            res += use_machine({0, i}) == 0;
        }
        return res;
    }

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);

    shuffle(p.begin() + 1, p.begin() + n, std::mt19937(std::random_device()()));

    vector<int> A = {0}, B;

    int k = 73;

    int i = 1;
    while (i < 3){
        if (use_machine({0, p[i]}) == 0) A.push_back(p[i]); else
            B.push_back(p[i]);
        i++;
    }

    while (i < 2 * k + 3){
        if (A.size() >= 2){
            int cnt = use_machine({A[0], p[i], A[1], p[i + 1]});
            if (cnt & 2) B.push_back(p[i]); else
                A.push_back(p[i]);
            if (cnt & 1) B.push_back(p[i + 1]); else
                A.push_back(p[i + 1]);
        } else {
            int cnt = use_machine({B[0], p[i], B[1], p[i + 1]});
            if (cnt & 2) A.push_back(p[i]); else
                B.push_back(p[i]);
            if (cnt & 1) A.push_back(p[i + 1]); else
                B.push_back(p[i + 1]);
        }
        i += 2;
    }

    int res = A.size();

    while (i < n){
        vector<int> r;
        if (A.size() > B.size()){
            for (int x : A){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(p[i]);
                i++;
            }

            int cnt = use_machine(r);
            if (cnt & 1) B.push_back(r.back()); else
                A.push_back(r.back());
            res += r.size() / 2 - (cnt + 1) / 2;
        } else {
            for (int x : B){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(p[i]);
                i++;
            }
            int cnt = use_machine(r);
            if (cnt & 1) A.push_back(r.back()); else
                B.push_back(r.back());
            res += (cnt + 1) / 2;
        }
    }

    return res;
}

Subtask #1

92.623 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	2 ms	200 KB	Output is correct
6	Correct	2 ms	200 KB	Output is correct
7	Correct	7 ms	328 KB	Output is correct
8	Correct	6 ms	328 KB	Output is correct
9	Correct	7 ms	392 KB	Output is correct
10	Correct	6 ms	328 KB	Output is correct
11	Partially correct	6 ms	392 KB	Output is partially correct
12	Correct	8 ms	392 KB	Output is correct
13	Correct	6 ms	384 KB	Output is correct
14	Correct	5 ms	344 KB	Output is correct
15	Partially correct	8 ms	456 KB	Output is partially correct
16	Partially correct	7 ms	312 KB	Output is partially correct
17	Correct	3 ms	456 KB	Output is correct
18	Correct	6 ms	328 KB	Output is correct
19	Partially correct	7 ms	396 KB	Output is partially correct
20	Correct	7 ms	328 KB	Output is correct
21	Correct	5 ms	408 KB	Output is correct
22	Partially correct	7 ms	328 KB	Output is partially correct
23	Correct	7 ms	328 KB	Output is correct
24	Correct	4 ms	328 KB	Output is correct
25	Partially correct	7 ms	328 KB	Output is partially correct
26	Partially correct	8 ms	400 KB	Output is partially correct
27	Partially correct	6 ms	384 KB	Output is partially correct
28	Partially correct	7 ms	408 KB	Output is partially correct
29	Partially correct	7 ms	328 KB	Output is partially correct
30	Partially correct	8 ms	396 KB	Output is partially correct
31	Partially correct	7 ms	328 KB	Output is partially correct
32	Partially correct	7 ms	328 KB	Output is partially correct
33	Partially correct	7 ms	412 KB	Output is partially correct
34	Partially correct	6 ms	408 KB	Output is partially correct
35	Partially correct	6 ms	400 KB	Output is partially correct
36	Partially correct	6 ms	408 KB	Output is partially correct
37	Partially correct	8 ms	392 KB	Output is partially correct
38	Partially correct	9 ms	400 KB	Output is partially correct
39	Partially correct	7 ms	392 KB	Output is partially correct
40	Partially correct	8 ms	388 KB	Output is partially correct
41	Partially correct	9 ms	400 KB	Output is partially correct
42	Partially correct	7 ms	456 KB	Output is partially correct
43	Partially correct	7 ms	388 KB	Output is partially correct
44	Partially correct	8 ms	400 KB	Output is partially correct
45	Partially correct	6 ms	328 KB	Output is partially correct
46	Partially correct	7 ms	328 KB	Output is partially correct
47	Partially correct	7 ms	408 KB	Output is partially correct
48	Partially correct	7 ms	460 KB	Output is partially correct
49	Partially correct	5 ms	412 KB	Output is partially correct
50	Partially correct	9 ms	328 KB	Output is partially correct
51	Partially correct	8 ms	332 KB	Output is partially correct
52	Partially correct	7 ms	328 KB	Output is partially correct
53	Partially correct	8 ms	328 KB	Output is partially correct
54	Partially correct	9 ms	328 KB	Output is partially correct
55	Partially correct	10 ms	404 KB	Output is partially correct
56	Partially correct	7 ms	392 KB	Output is partially correct
57	Partially correct	7 ms	328 KB	Output is partially correct
58	Partially correct	7 ms	392 KB	Output is partially correct
59	Partially correct	10 ms	392 KB	Output is partially correct
60	Partially correct	9 ms	328 KB	Output is partially correct
61	Partially correct	7 ms	408 KB	Output is partially correct
62	Correct	0 ms	200 KB	Output is correct
63	Correct	0 ms	200 KB	Output is correct
64	Correct	0 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	0 ms	200 KB	Output is correct
68	Correct	0 ms	200 KB	Output is correct
69	Correct	0 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	0 ms	200 KB	Output is correct
73	Correct	0 ms	200 KB	Output is correct
74	Correct	0 ms	200 KB	Output is correct
75	Correct	0 ms	200 KB	Output is correct
76	Correct	1 ms	200 KB	Output is correct
77	Correct	0 ms	200 KB	Output is correct
78	Correct	1 ms	200 KB	Output is correct
79	Correct	0 ms	200 KB	Output is correct
80	Correct	1 ms	200 KB	Output is correct
81	Correct	0 ms	200 KB	Output is correct
82	Correct	1 ms	200 KB	Output is correct
83	Correct	0 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	0 ms	200 KB	Output is correct
87	Correct	0 ms	200 KB	Output is correct
88	Correct	0 ms	200 KB	Output is correct
89	Correct	0 ms	200 KB	Output is correct
90	Correct	0 ms	212 KB	Output is correct
91	Correct	1 ms	204 KB	Output is correct