답안 #605141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605141	2022-07-25T13:21:00 Z	Mher	버섯 세기 (IOI20_mushrooms)	C++14	79.8587 / 100	9 ms	392 KB

mushrooms

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

using namespace std;

const int M = 251;

/*
5
0 1 1 0 1
*/


int count_mushrooms(int n) {
	vector<int> cl(n, -1);
	cl[0] = 1;
	if (n == 2)
    {
        return 2 - use_machine({0, 1});
    }
    cl[1] = 1 - use_machine({0, 1});
    cl[2] = 1 - use_machine({0, 2});
    bool t;
    int x, y;
    if (cl[0] == cl[1])
    {
        t = true;
        x = 0;
        y = 1;
    }
    else if (cl[0] == cl[2])
    {
        t = true;
        x = 0;
        y = 2;
    }
    else
    {
        t = false;
        x = 1;
        y = 2;
    }
    for (int i = 3; i < min(n - 1, M); i += 2)
    {
        int res = use_machine({x, i, y, i + 1});
        if (res == 0)
        {
            cl[i] = cl[i + 1] = t;
        }
        else if (res == 1)
        {
            cl[i] = t;
            cl[i + 1] = !t;
        }
        else if (res == 2)
        {
            cl[i] = !t;
            cl[i + 1] = t;
        }
        else
        {
            cl[i] = cl[i + 1] = !t;
        }
    }
    if (n < M && n % 2 == 0)
    {
        cl[n - 1] = 1 - use_machine({0, n - 1});
    }
    int ans = 0;
    if (n < M)
    {
        for (int i = 0; i < n; i++)
            ans += cl[i];
        return ans;
    }
    int as = 0;
    for (int i = 0; i < M; i++)
    {
        as += cl[i];
    }
    ans += as;
    bool cs = as > M / 2;
    vector<int> ch;
    for (int i = 0; i < M; i++)
    {
        if (cl[i] == cs)
        {
            //cout << i << endl;
            ch.push_back(i);
        }
    }
    if (ch.size() % 2 == 1)
    {
        ch.pop_back();
    }
    int len = ch.size();
    for (int i = M; i < n; i += len)
    {
        vector<int> q;
        for (int j = 0; j < min(len, n - i); j++)
        {
            q.push_back(ch[j]);
            q.push_back(i + j);
        }
        int res = use_machine(q);
        int ab = res / 2, rm = res % 2;
        ab += rm;
        ans += cs ? min(len, n - i) - ab : ab;
    }
    return ans;
}

Subtask #1

79.8587 / 100.0

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