Submission #432030

#	Time	Username	Problem	Language	Result	Execution time	Memory
432030		Ozy	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	11 ms	328 KiB

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 (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