Submission #314700

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

mushrooms

// WIP: REFACTORING

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

using namespace std;

const int M = 100;

bool swapped;
int i, just_count_A, just_count_B;
vector<int> A, B;


void make_swap() {
    swapped = not swapped;
    swap(just_count_A, just_count_B);
    swap(A, B);
}


bool decide_swap() {
    if (A.size() < B.size()) {
        make_swap();
    }
    return true;
}


int handle_parity(int parity) {
    (parity == 0 ? A : B).push_back(i);
    return 1;
}


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


void get_mixed_three_two_pivots() {
    while (decide_swap() and (A.size() < 3 or B.size() < 2) and (A.size() < M)) {
        int result = use_machine({ i, A[0], i+1, A[1] });
        i += handle_parity(result%2);
        i += handle_parity(result/2);
    }
}


void get_four_pivots_from_conflict_two() {
    switch (use_machine({ B[0], i, B[1], A[0], i+1, A[1], i+2, A[2], i+3 })) {
        case 1:
            A.insert(A.end(), { i+1, i+2, i+3 });
            B.insert(B.end(), { i });
            break;
        case 2:
            A.insert(A.end(), { i+1, i+2 });
            B.insert(B.end(), { i, i+3 });
            break;
        case 3:
            A.insert(A.end(), { i+1, i+3 });
            B.insert(B.end(), { i, i+2 });
            break;
        case 4:
            A.insert(A.end(), { i+1 });
            B.insert(B.end(), { i, i+2, i+3 });
            break;
        case 5:
            A.insert(A.end(), { i, i+2, i+3 });
            B.insert(B.end(), { i+1 });
            break;
        case 6:
            A.insert(A.end(), { i, i+2 });
            B.insert(B.end(), { i+1, i+3 });
            break;
        case 7:
            A.insert(A.end(), { i, i+3 });
            B.insert(B.end(), { i+1, i+2 });
            break;
        default:    // TODO XXX FIXME PLS NO DEFAULT!!
            A.insert(A.end(), { i });
            B.insert(B.end(), { i+1, i+2, i+3 });
    }
}


int handle_pair(int result) {
    switch (result - result%2) {
        case 0:
            A.insert(A.end(), { i, i+1 });
            return 2;
        case 4:
            B.insert(B.end(), { i, i+1 });
            return 2;
        case 2: default:
            get_four_pivots_from_conflict_two();
            return 4;
    }
}


void get_same_many_pivots() {   // TODO argument: limits
    // TODO M is somewhat magic number, can we determine them in term of n?
    while (decide_swap() and A.size() < M) {
        int result = use_machine({ i, A[0], i+1, A[1], i+2, A[2] });
        i += handle_parity(result%2);
        i += handle_pair(result);
    }
}


vector<int> make_sample(int size) {
    vector<int> sample = { };
    for (int j=0; j<size; j++) {
        sample.insert(sample.end(), { i+j, A[j] });
    }
    return sample;
}


void count_the_rest(int n) {
    while (i < n) {
        decide_swap();
        int test_size = min((int)A.size(), n-i);
        int result = use_machine(make_sample(test_size));
        i += handle_parity(result%2);
        i += test_size-1;
        just_count_A += (test_size-1) - (result/2);
        just_count_B += result/2;
    }
    if (swapped) {
        make_swap();
    }
}


void count_naive(int n) {
    while (i < n) {
        i += handle_parity(use_machine({ A[0], i }));
    }
}


void init_variables() {
    swapped = false;
    i = 1;
    just_count_A = just_count_B = 0;
    A = { 0 };
    B = { };
}


int count_mushrooms(int n) {
    init_variables();
    if (n <= 226) {
        count_naive(n);
    } else {
        get_same_two_pivots();
        get_mixed_three_two_pivots();
        get_same_many_pivots();
        count_the_rest(n);
    }
    return A.size() + just_count_A;
}

• Subtask 1: 100 / 100