Submission #314674

#	Time	Username	Problem	Language	Result	Execution time	Memory
314674		neizod	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	10 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 count_A, count_B, i;



void partV1() {
    while (count_A < 2 && count_B < 2) {
        vector<int> x = { 0, i };
        int result = use_machine(x);
        if (result == 0) {
            A.push_back(i);
            count_A++;
        }
        else{
            B.push_back(i);
            count_B++;
        }
        i++;
    }
}


void partV2() {
    // TODO refactor while condition
    while ((count_A < 3 || count_B < 2) && (count_A < 2 || count_B < 3) && count_A < M && count_B < M) {
        bool swapped = false;
        if (count_A < count_B) {
            swapped = true;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x = { i, A[0], i+1, A[1] };
        int result = use_machine(x);
        switch (result) {
            case 0:
                A.push_back(i);
                A.push_back(i+1);
                count_A += 2;
                break;
            case 1:
                B.push_back(i);
                A.push_back(i+1);
                count_A++;
                count_B++;
                break;
            case 2:
                A.push_back(i);
                B.push_back(i+1);
                count_A++;
                count_B++;
                break;
            default:
                B.push_back(i);
                B.push_back(i+1);
                count_B += 2;
        }
        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
        i += 2;
    }
}


void partV3() {
    // TODO M is somewhat magic number, can we determine them in term of n?
    while (count_A < M && count_B < M) {
        bool swapped = false;
        if (count_A < count_B) {
            swapped = true;
            swap(A, B);
            swap(count_A, count_B);
        }
        vector<int> x = { i, A[0], i+1, A[1], i+2, A[2] };
        int result = use_machine(x);
        if (result%2 == 0) {
            A.push_back(i);
            count_A++;
        } else {
            B.push_back(i);
            count_B++;
        }

        if (result-result%2 == 0) {
            A.push_back(i+1);
            A.push_back(i+2);
            count_A += 2;
            i += 3;
        } else if (result-result%2 == 4) {
            B.push_back(i+1);
            B.push_back(i+2);
            count_B += 2;
            i += 3;
        } else {
            vector<int> x = { B[0], i+1, B[1], A[0], i+2, A[1], i+3, A[2], i+4 };
            int result = use_machine(x);
            switch (result) {
                case 1:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 2:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 3:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 4:
                    B.push_back(i+1);
                    A.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
                    break;
                case 5:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 3;
                    count_B += 1;
                    break;
                case 6:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    A.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                case 7:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    A.push_back(i+4);
                    count_A += 2;
                    count_B += 2;
                    break;
                default:
                    A.push_back(i+1);
                    B.push_back(i+2);
                    B.push_back(i+3);
                    B.push_back(i+4);
                    count_A += 1;
                    count_B += 3;
            }
            i += 5;
        }

        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
    }
}


void partV4(int n) {
    while (i < n) {
        bool swapped = false;
        if (A.size() < B.size()) {
            swapped = true;
            swap(A, B);
            swap(count_A, count_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);
        if (result%2 == 0) {
            A.push_back(i);
            count_A++;
        } else {
            B.push_back(i);
            count_B++;
        }
        count_B += result/2;
        count_A += (L-1) - result/2;

        if (swapped) {
            swap(A, B);
            swap(count_A, count_B);
        }
        i += L;
    }
}


int naive(int n) {
    while (i < n) {
        vector<int> x;
        x.push_back(0);
        x.push_back(i);
        int result = use_machine(x);
        if (result == 0 ) {
            A.push_back(i);
            count_A++;
        } else {
            B.push_back(i);
            count_B++;
        }
        i++;
    }
    return count_A;
}


int count_mushrooms(int n) {
    A = { 0 };
    B = { };
    count_A = 1;
    count_B = 0;
    i = 1;
    if (n <= 226) {
        return naive(n);
    }
    partV1();
    partV2();
    partV3();
    partV4(n);
    return count_A;
}

• Subtask 1: 100 / 100