Submission #314722

#	Time	Username	Problem	Language	Result	Execution time	Memory
314722		neizod	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	11 ms	512 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);
    }
}


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(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_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);
        try {
            i += handle_pair(result);
        } catch (int e) {
            i += handle_conflict(use_machine({ B[0], i, B[1], A[0], i+1, A[1], i+2, A[2], i+3 }));
        }
    }
}


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