Submission #314862

#	Time	Username	Problem	Language	Result	Execution time	Memory
314862		neizod	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	12 ms	672 KiB

mushrooms

// WIP: REFACTORING

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

using namespace std;

const int M = 100;  // TODO magic number! can we determine them in term of n?

bool swapped = false;
int i = 1;
int just_count_A = 0;
int just_count_B = 0;
vector<int> A = { 0 };
vector<int> 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;
}


int handle_pair(int result) {
    int even = result - (result%2);
    if (even == 2) {
        throw 4;
    }
    (even == 0 ? A : B).push_back(i);
    (even == 0 ? A : B).push_back(i+1);
    return 2;
}


int handle_conflict_pair(int result) {
    int flag = result - 1;
    (flag & 0b100 ? A : B).push_back(i);
    (flag & 0b100 ? B : A).push_back(i+1);
    (flag & 0b010 ? B : A).push_back(i+2);
    (flag & 0b001 ? B : A).push_back(i+3);
    return 4;
}


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


void get_same_many_pivots() {
    int result;
    while (decide_swap() and A.size() < M) {
        if (A.size() < 3 or B.size() < 2) {
            result = use_machine({ i, A[0], i+1, A[1] });
            i += handle_parity(result%2);
            i += handle_parity(result/2);
        } else {
            result = use_machine({ i, A[0], i+1, A[1], i+2, A[2] });
            i += handle_parity(result%2);
            try {
                i += handle_pair(result);
            } catch (int e) {
                result = use_machine({ B[0], i, B[1], A[0], i+1, A[1], i+2, A[2], i+3 });
                i += handle_conflict_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 (decide_swap() and i < n) {
        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;
    }
}


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


/*
void init_variables() {     // program run only once? move this to header?
    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_same_many_pivots();
        count_the_rest(n);
    }
    if (swapped) {
        make_swap();
    }
    return A.size() + just_count_A;
}

• Subtask 1: 100 / 100