Submission #432039

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432039	2021-06-17T19:20:44 Z	Ozy	Counting Mushrooms (IOI20_mushrooms)	C++17	80.427 / 100	10 ms	304 KB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define lli int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

lli as,bs,pos,p,tam,y,res;
vector<lli> A,B,arr,ult;

lli busca(lli raiz, lli tipo) {

    vector<lli> llamada;
    llamada = vector<lli> (4, 0);

    if (tipo == 1) llamada[0] = A[0], llamada[2] = A[1];
    else  llamada[0] = B[0], llamada[2] = B[1];

    lli x,pos = 3;

    while (as < raiz && bs < raiz) {
        llamada[1] = pos++;
        llamada[3] = pos++;

        x = use_machine(llamada);
        if (tipo == 1) {
            if (x == 0) {as += 2; A.push_back(pos-2); A.push_back(pos-1);}
            else if (x == 1) {as++; A.push_back(pos-2); bs++; B.push_back(pos-1);}
            else if (x == 2) {as++; A.push_back(pos-1); bs++; B.push_back(pos-2);}
            else {bs += 2; B.push_back(pos-2); B.push_back(pos-1);}
        }
        else {
            if (x == 0) {bs += 2; B.push_back(pos-2); B.push_back(pos-1);}
            else if (x == 1) {as++; A.push_back(pos-1); bs++; B.push_back(pos-2);}
            else if (x == 2) {as++; A.push_back(pos-2); bs++; B.push_back(pos-1);}
            else {as += 2; A.push_back(pos-2); A.push_back(pos-1);}
        }
    }

    if (as > bs) return 1;
    else return 2;
}

int count_mushrooms(int n) {

    as = 1;
    bs = 0;
    if (n == 2) {
        p = use_machine({0,1});
        if (p == 1) return 1;
        else return 2;
    }

    p = use_machine({0,1});
    if (p == 0) A.push_back(1), as++;
    else B.push_back(1), bs++;

    p = use_machine({0,2});
    if (p == 0) A.push_back(2), as++;
    else B.push_back(2), bs++;


    p = sqrt(n);
    if (p > 3) p++;
    if (as >= 2) p = busca(p,1);
    else p = busca(p,2);


    if (p == 1) {
        arr.resize(as*2);
        lli pos = 0;
        for(auto act : A) {arr[pos] = act; pos += 2;}
        //rep(i,0,(as*2)-1) cout << arr[i] << ' ';
    }
    else {
        arr.resize(bs*2);
        lli pos = 0;
        for(auto act : B) {arr[pos] = act; pos += 2;}
        //rep(i,0,(bs*2)-1) cout << arr[i] << ' ';
    }
    //cout  << endl;


    pos = as+bs;
    res = as;

    while (pos < n) {
        if (p == 1) {
            if (n-pos < as) break;

            y = 1;
            rep(i,0,as-1) {arr[y] = pos++; y+=2;}

            y = use_machine(arr);
            y++;
            y/=2;
            y = as-y;
            res += y;
        }
        else {
            if (n-pos < bs) break;

            y = 1;
            rep(i,0,bs-1) {arr[y] = pos++; y+=2;}

            y = use_machine(arr);
            y++;
            y/=2;
            res += y;
        }
    }

    if (pos < n) {
        ult.resize((n-pos)*2);
        y = pos;
        rep(i,0,((n-pos)*2)-1) {
            if ((i%2) == 0) ult[i] = arr[i];
            else {
                ult[i] = y;
                y++;
            }
        }

        y = use_machine(ult);
        y++;
        y /= 2;
        if (p == 1) y = (n-pos)-y;
        res += y;
    }

    return res;
}

Subtask #1

80.427 / 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	1 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	7 ms	200 KB	Output is correct
8	Correct	7 ms	200 KB	Output is correct
9	Correct	9 ms	200 KB	Output is correct
10	Partially correct	7 ms	200 KB	Output is partially correct
11	Partially correct	9 ms	200 KB	Output is partially correct
12	Partially correct	7 ms	200 KB	Output is partially correct
13	Correct	8 ms	200 KB	Output is correct
14	Correct	4 ms	200 KB	Output is correct
15	Partially correct	7 ms	200 KB	Output is partially correct
16	Partially correct	7 ms	200 KB	Output is partially correct
17	Correct	4 ms	200 KB	Output is correct
18	Correct	7 ms	200 KB	Output is correct
19	Partially correct	9 ms	200 KB	Output is partially correct
20	Partially correct	7 ms	200 KB	Output is partially correct
21	Partially correct	7 ms	200 KB	Output is partially correct
22	Partially correct	9 ms	200 KB	Output is partially correct
23	Partially correct	6 ms	200 KB	Output is partially correct
24	Correct	6 ms	200 KB	Output is correct
25	Partially correct	8 ms	200 KB	Output is partially correct
26	Partially correct	7 ms	200 KB	Output is partially correct
27	Partially correct	9 ms	200 KB	Output is partially correct
28	Partially correct	9 ms	200 KB	Output is partially correct
29	Partially correct	6 ms	300 KB	Output is partially correct
30	Partially correct	7 ms	200 KB	Output is partially correct
31	Partially correct	6 ms	300 KB	Output is partially correct
32	Partially correct	8 ms	200 KB	Output is partially correct
33	Partially correct	7 ms	200 KB	Output is partially correct
34	Partially correct	7 ms	304 KB	Output is partially correct
35	Partially correct	7 ms	200 KB	Output is partially correct
36	Partially correct	7 ms	200 KB	Output is partially correct
37	Partially correct	6 ms	304 KB	Output is partially correct
38	Partially correct	7 ms	200 KB	Output is partially correct
39	Partially correct	6 ms	300 KB	Output is partially correct
40	Partially correct	7 ms	304 KB	Output is partially correct
41	Partially correct	7 ms	200 KB	Output is partially correct
42	Partially correct	10 ms	304 KB	Output is partially correct
43	Partially correct	7 ms	200 KB	Output is partially correct
44	Partially correct	6 ms	300 KB	Output is partially correct
45	Partially correct	9 ms	200 KB	Output is partially correct
46	Partially correct	9 ms	200 KB	Output is partially correct
47	Partially correct	8 ms	200 KB	Output is partially correct
48	Partially correct	7 ms	200 KB	Output is partially correct
49	Partially correct	10 ms	200 KB	Output is partially correct
50	Partially correct	7 ms	200 KB	Output is partially correct
51	Partially correct	8 ms	200 KB	Output is partially correct
52	Partially correct	9 ms	200 KB	Output is partially correct
53	Partially correct	7 ms	304 KB	Output is partially correct
54	Partially correct	8 ms	200 KB	Output is partially correct
55	Partially correct	8 ms	200 KB	Output is partially correct
56	Partially correct	8 ms	200 KB	Output is partially correct
57	Partially correct	7 ms	200 KB	Output is partially correct
58	Partially correct	7 ms	200 KB	Output is partially correct
59	Partially correct	7 ms	200 KB	Output is partially correct
60	Partially correct	7 ms	200 KB	Output is partially correct
61	Partially correct	8 ms	200 KB	Output is partially correct
62	Correct	0 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	0 ms	200 KB	Output is correct
67	Correct	0 ms	200 KB	Output is correct
68	Correct	1 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	0 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	1 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	1 ms	200 KB	Output is correct
78	Correct	0 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	1 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	1 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	1 ms	200 KB	Output is correct
90	Correct	1 ms	200 KB	Output is correct
91	Correct	0 ms	200 KB	Output is correct