Submission #314693

#	Time	Username	Problem	Language	Result	Execution time	Memory
314693		neizod	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	9 ms	384 KiB

mushrooms

// WIP: REFACTORING

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

using namespace std;

const int M = 100;

vector<int> A, B;
int just_A, just_B, i;


void handle_parity(int parity) {
    if (parity == 0) {
        A.push_back(i);
    } else {
        B.push_back(i);
    }
    i += 1;
}


void get_same_two_pivots() {
    while (A.size() < 2 and B.size() < 2) {
        handle_parity(use_machine({ 0, i }));
    }
}


void get_mixed_three_two_pivots() {
    // TODO refactor while condition --> can use do-until
    while ( (A.size() < 3 or B.size() < 2) and
            (A.size() < 2 or B.size() < 3) and
            (A.size() < M and B.size() < M) ) {
        bool swapped = false;
        if (A.size() < B.size()) {
            swapped = true;     // swapped = not swapped
            swap(A, B);
        }
        int result = use_machine({ i, A[0], i+1, A[1] });
        handle_parity(result%2);
        handle_parity(result/2);
        if (swapped) {
            swapped = not swapped;
            swap(A, B);
        }
    }
}


void get_same_many_pivots() {   // TODO argument: limits
    // TODO M is somewhat magic number, can we determine them in term of n?
    while (A.size() < M && B.size() < M) {
        bool swapped = false;
        if (A.size() < B.size()) {
            swapped = true;
            swap(A, B);
        }
        int result = use_machine({ i, A[0], i+1, A[1], i+2, A[2] });
        int parity = result % 2;
        switch (parity) {
            case 0:
                A.push_back(i);
                break;
            case 1:
                B.push_back(i);
                break;
        }
        switch (result - parity) {
            case 0:
                A.insert(A.end(), { i+1, i+2 });
                i += 3;
                break;
            case 4:
                B.insert(B.end(), { i+1, i+2 });
                i += 3;
                break;
            case 2:
                switch (use_machine({ B[0], i+1, B[1], A[0], i+2, A[1], i+3, A[2], i+4 })) {
                    case 1:
                        A.insert(A.end(), { i+2, i+3, i+4 });
                        B.insert(B.end(), { i+1 });
                        break;
                    case 2:
                        A.insert(A.end(), { i+2, i+3 });
                        B.insert(B.end(), { i+1, i+4 });
                        break;
                    case 3:
                        A.insert(A.end(), { i+2, i+4 });
                        B.insert(B.end(), { i+1, i+3 });
                        break;
                    case 4:
                        A.insert(A.end(), { i+2 });
                        B.insert(B.end(), { i+1, i+3, i+4 });
                        break;
                    case 5:
                        A.insert(A.end(), { i+1, i+3, i+4 });
                        B.insert(B.end(), { i+2 });
                        break;
                    case 6:
                        A.insert(A.end(), { i+1, i+3 });
                        B.insert(B.end(), { i+2, i+4 });
                        break;
                    case 7:
                        A.insert(A.end(), { i+1, i+4 });
                        B.insert(B.end(), { i+2, i+3 });
                        break;
                    default:    // TODO XXX FIXME PLS NO DEFAULT!!
                        A.insert(A.end(), { i+1 });
                        B.insert(B.end(), { i+2, i+3, i+4 });
                }
                i += 5;
        }
        if (swapped) {
            swap(A, B);
        }
    }
}


void count_the_rest(int n) {
    while (i < n) {
        bool swapped = false;
        if (A.size() < B.size()) {
            swapped = true;
            swap(A, B);
            swap(just_A, just_B);
        }
        vector<int> x;
        int L = min((int)A.size(), n-i);
        for (int j=0; j<L; j++) {
            x.push_back(i+j);
            x.push_back(A[j]);
        }
        int result = use_machine(x);
        int parity = result % 2;
        if (parity == 0) {
            A.push_back(i);
        } else {
            B.push_back(i);
        }
        just_A += (L-1) - result/2;
        just_B += result/2;
        if (swapped) {
            swap(A, B);
            swap(just_A, just_B);
        }
        i += L;
    }
}


int naive(int n) {
    while (i < n) {
        handle_parity(use_machine({ 0, i }));
    }
    return A.size();
}


int count_mushrooms(int n) {
    i = 1;
    just_A = just_B = 0;
    A = { 0 };
    B = { };
    if (n <= 226) {
        return naive(n);
    }
    get_same_two_pivots();
    get_mixed_three_two_pivots();
    get_same_many_pivots();
    count_the_rest(n);
    return A.size() + just_A;
}

• Subtask 1: 100 / 100