Submission #314869

#	Time	Username	Problem	Language	Result	Execution time	Memory
314869		neizod	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	11 ms	512 KiB

mushrooms

// WIP: REFACTORING

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

using namespace std;


bool swapped = false;
int i = 1;
int just_count_A = 0;
int just_count_B = 0;
vector<int> A = { 0 };
vector<int> B = { };


int calc_pivots_limits(int n) {
    return 1 + (3*sqrt(n)/4);
}


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_pivots(int limits) {
    int result;
    while (decide_swap() and (int)A.size() < limits) {
        if (A.size() < 2 and B.size() < 2) {
            i += handle_parity(use_machine({ i, A[0] }));
        } else 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({ i, A[0] }));
    }
}


int count_mushrooms(int n) {
    int limits = calc_pivots_limits(n);
    //if (n <= 226) {
    //    count_naive(n);
    //} else {
        get_pivots(limits);
        count_the_rest(n);
    //}
    if (swapped) {
        make_swap();
    }
    return A.size() + just_count_A;
}

• Subtask 1: 0 / 100