Submission #357839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
357839	2021-01-24T19:02:01 Z	doowey	Counting Mushrooms (IOI20_mushrooms)	C++14	80.427 / 100	11 ms	512 KB

mushrooms

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

using namespace std;

const int N = 20000;

int get_opt(){
    int low = 10000;
    int id = 1;
    for(int k = 1; k <= 300; k ++ ){
        if(k + (N - 2 * k + (k - 1)) / k < low){
            low = k + (N - 2 * k + (k - 1)) / k;
            id = k;
        }
    }
    return id;
}
const int K = get_opt();



int count_mushrooms(int n) {

	int cnt = 1;
    if(n <= 226){
        int cur;
        for(int i = 1; i < n; i ++ ){
            cur = use_machine({0, i});
            if(cur == 0) cnt ++ ;
        }
        return cnt;
    }
    vector<int> q[2];
    q[0].push_back(0);
    int id = 1;
    int A, B, C, D;
    int f;
    int cur;
    while(max(q[0].size(),q[1].size()) <= K){
        if(q[0].size() < 2 && q[1].size() < 2){
            cur = use_machine({0, id});
            if(cur == 0){
                q[0].push_back(id);
            }
            else{
                q[1].push_back(id);
            }
            id ++ ;
        }
        else{
            if(q[0].size() >= 2){
                f = 0;
                A = q[0][0];
                B = q[0][1];
            }
            else{
                f = 1;
                A = q[1][0];
                B = q[1][1];
            }
            C = id;
            D = id + 1;
            id += 2;
            cur = use_machine({A, C, B, D});
            if(cur == 0){
                q[f].push_back(C);
                q[f].push_back(D);
            }
            else if(cur == 1){
                q[f].push_back(C);
                q[f^1].push_back(D);
            }
            else if(cur == 2){
                q[f^1].push_back(C);
                q[f].push_back(D);
            }
            else{
                q[f^1].push_back(C);
                q[f^1].push_back(D);
            }
        }
    }
    int lim = max(q[0].size(), q[1].size());
    int fa = 0;
    if(q[1].size() == lim) fa = 1;
    vector<int> ids;
    int soln = q[0].size();
    int gg;
    int sz;
    int c1;
    for(int i = id; i < n ; i ++ ){
        ids.push_back(i);
        if(ids.size() == lim || i + 1 == n){
            vector<int> qr;
            sz = (int)ids.size();
            for(int t = 0; t < ids.size(); t ++ ){
                qr.push_back(ids[t]);
                qr.push_back(q[fa][t]);
            }
            gg = use_machine(qr);
            if(fa == 0){
                c1 = (gg + 1) / 2;
                soln += sz - c1;
            }
            else{
                soln += (gg + 1) / 2;
            }
            ids.clear();
        }
    }
    return soln;
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:40:40: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'const int' [-Wsign-compare]
   40 |     while(max(q[0].size(),q[1].size()) <= K){
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:86:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |     if(q[1].size() == lim) fa = 1;
      |        ~~~~~~~~~~~~^~~~~~
mushrooms.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         if(ids.size() == lim || i + 1 == n){
      |            ~~~~~~~~~~~^~~~~~
mushrooms.cpp:97:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(int t = 0; t < ids.size(); t ++ ){
      |                            ~~^~~~~~~~~~~~

Subtask #1

80.427 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	512 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	3 ms	364 KB	Output is correct
7	Correct	7 ms	364 KB	Output is correct
8	Correct	7 ms	364 KB	Output is correct
9	Correct	7 ms	364 KB	Output is correct
10	Partially correct	8 ms	364 KB	Output is partially correct
11	Partially correct	8 ms	364 KB	Output is partially correct
12	Partially correct	8 ms	364 KB	Output is partially correct
13	Correct	8 ms	364 KB	Output is correct
14	Correct	5 ms	364 KB	Output is correct
15	Partially correct	7 ms	364 KB	Output is partially correct
16	Partially correct	8 ms	364 KB	Output is partially correct
17	Correct	4 ms	364 KB	Output is correct
18	Correct	7 ms	384 KB	Output is correct
19	Partially correct	8 ms	364 KB	Output is partially correct
20	Partially correct	7 ms	364 KB	Output is partially correct
21	Partially correct	7 ms	364 KB	Output is partially correct
22	Partially correct	8 ms	364 KB	Output is partially correct
23	Partially correct	7 ms	364 KB	Output is partially correct
24	Correct	5 ms	364 KB	Output is correct
25	Partially correct	8 ms	364 KB	Output is partially correct
26	Partially correct	10 ms	364 KB	Output is partially correct
27	Partially correct	9 ms	364 KB	Output is partially correct
28	Partially correct	8 ms	364 KB	Output is partially correct
29	Partially correct	7 ms	388 KB	Output is partially correct
30	Partially correct	7 ms	364 KB	Output is partially correct
31	Partially correct	8 ms	364 KB	Output is partially correct
32	Partially correct	7 ms	364 KB	Output is partially correct
33	Partially correct	11 ms	364 KB	Output is partially correct
34	Partially correct	9 ms	364 KB	Output is partially correct
35	Partially correct	7 ms	364 KB	Output is partially correct
36	Partially correct	8 ms	364 KB	Output is partially correct
37	Partially correct	10 ms	364 KB	Output is partially correct
38	Partially correct	8 ms	364 KB	Output is partially correct
39	Partially correct	11 ms	364 KB	Output is partially correct
40	Partially correct	8 ms	364 KB	Output is partially correct
41	Partially correct	8 ms	364 KB	Output is partially correct
42	Partially correct	7 ms	364 KB	Output is partially correct
43	Partially correct	7 ms	364 KB	Output is partially correct
44	Partially correct	8 ms	364 KB	Output is partially correct
45	Partially correct	7 ms	364 KB	Output is partially correct
46	Partially correct	8 ms	364 KB	Output is partially correct
47	Partially correct	8 ms	364 KB	Output is partially correct
48	Partially correct	7 ms	364 KB	Output is partially correct
49	Partially correct	8 ms	364 KB	Output is partially correct
50	Partially correct	9 ms	364 KB	Output is partially correct
51	Partially correct	9 ms	364 KB	Output is partially correct
52	Partially correct	8 ms	364 KB	Output is partially correct
53	Partially correct	8 ms	364 KB	Output is partially correct
54	Partially correct	7 ms	364 KB	Output is partially correct
55	Partially correct	8 ms	312 KB	Output is partially correct
56	Partially correct	8 ms	364 KB	Output is partially correct
57	Partially correct	8 ms	364 KB	Output is partially correct
58	Partially correct	8 ms	384 KB	Output is partially correct
59	Partially correct	9 ms	364 KB	Output is partially correct
60	Partially correct	7 ms	388 KB	Output is partially correct
61	Partially correct	10 ms	364 KB	Output is partially correct
62	Correct	0 ms	364 KB	Output is correct
63	Correct	0 ms	364 KB	Output is correct
64	Correct	0 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	0 ms	364 KB	Output is correct
68	Correct	0 ms	364 KB	Output is correct
69	Correct	0 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	1 ms	364 KB	Output is correct
73	Correct	0 ms	364 KB	Output is correct
74	Correct	0 ms	364 KB	Output is correct
75	Correct	1 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	0 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	0 ms	364 KB	Output is correct
84	Correct	0 ms	364 KB	Output is correct
85	Correct	0 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	1 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