Submission #1157124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157124		Nailuj_217	Counting Mushrooms (IOI20_mushrooms)	C++20	96.58 / 100	4 ms	732 KiB

mushrooms

#include <bits/stdc++.h>
#define l int 
using namespace std;


#include "mushrooms.h"


vector<l> positions;
vector<l> cocaine;
vector<l> flour;

l threshold = 140;
l uses = 0;

l machine(vector<l> a) {
    uses++;
    return use_machine(a);
}


void psh(vector<l>* a, vector<l> b) {
    a->insert(a->end(), b.begin(), b.end());
}

void psh_unequal(vector<l>* fs, vector<l>* sec, vector<l> elements) {
    for (int i = 0; i < elements.size(); i++) {
        if (i&1) sec->push_back(elements[i]);
        else fs->push_back(elements[i]);
    }
}

pair<vector<l>*, vector<l>*> return_bigger() {
    if (cocaine.size() > flour.size()) return {&cocaine, &flour};
    else return {&flour, &cocaine};
}

pair<vector<l>*, vector<l>*> get_two() {
    l result;
    while (cocaine.size() < 2 && flour.size() < 2) {
        result = machine({0, positions.back()});
        if (result == 0) cocaine.push_back(positions.back());
        else flour.push_back(positions.back());
        positions.pop_back();
    }
    return return_bigger();
}

pair<vector<l>*, vector<l>*> get_amount_by_two(l n) {
    auto [same, different] = get_two();
    l a, b, result;
    while (positions.size() > 1 && cocaine.size() < n && flour.size() < n) {
        a = positions.back(); positions.pop_back();
        b = positions.back(); positions.pop_back();
        result = machine({(*same)[0], a, (*same)[1], b});
        if (result == 0) {
            same->insert(same->end(), {a, b});
        } else if (result == 1) {
            same->push_back(a);
            different->push_back(b);
        } else if (result == 2) {
            same->push_back(b);
            different->push_back(a);
        } else {
            different->insert(different->end(), {a, b});
        }
    }
    if (cocaine.size() < n && flour.size() < n && positions.size() == 1) {
        result = machine({0, positions.back()});
        if (result == 0) cocaine.push_back(positions.back());
        else flour.push_back(positions.back());
        positions.pop_back();
    }
    
    return return_bigger();
}

pair<vector<l>*, vector<l>*> get_amount(l n, vector<l>* same, vector<l>* different) {
    l a, b, c, d, result;
    vector<vector<l>> unequal;

    while (positions.size() > 2 && cocaine.size() < n && flour.size() < n) {
        a = positions.back(); positions.pop_back();
        b = positions.back(); positions.pop_back();
        c = positions.back(); positions.pop_back();
        result = machine({(*same)[0], a, (*same)[1], b, (*same)[2], c});
        if (result == 0) {
            psh(same, {a, b, c}); 
        } else if (result == 1) {
            psh(same, {a, b});
            psh(different, {c});
        } else if (result == 4) {
            psh(same, {c});
            psh(different, {a, b});
        } else if (result == 5) {
            psh(different, {a, b, c});
        } else {
            if (result == 2) psh(same, {c});
            else psh(different, {c});
            unequal.push_back({a, b});
            n--;
        }
    }

    if (cocaine.size() < n && flour.size() < n && !positions.empty()) {
        get_amount_by_two(n);
    }
    vector<l> x, y, z;

    while (unequal.size() > 2) {
        x = unequal.back(); unequal.pop_back(); 
        y = unequal.back(); unequal.pop_back(); 
        z = unequal.back(); unequal.pop_back(); 
        result = machine({(*same)[0], x[0], (*same)[1], y[0], (*same)[2], z[0]});
        
        if (result == 0) {
            psh_unequal(same, different, x);
            psh_unequal(same, different, y);
            psh_unequal(same, different, z);
        } else if (result == 1) {
            psh_unequal(same, different, x);
            psh_unequal(same, different, y);
            psh_unequal(different, same, z);
        } else if (result == 4) {
            psh_unequal(different, same, x);
            psh_unequal(different, same, y);
            psh_unequal(same, different, z);
        } else if (result == 5) {
            psh_unequal(different, same, x);
            psh_unequal(different, same, y);
            psh_unequal(different, same, z);
        } else {
            if (result == 2) psh_unequal(same, different, z);
            else psh_unequal(different, same, z);
            reverse(x.begin(), x.end());
            x.insert(x.end(), y.begin(), y.end());
            unequal.push_back(x);
        }
    }
    if (unequal.size() == 2) {
        x = unequal.back(); unequal.pop_back(); 
        y = unequal.back(); unequal.pop_back(); 
        result = use_machine({(*same)[0], x[0], (*same)[1], y[0]});

        if (result&1) psh_unequal(different, same, y);
        else psh_unequal(same, different, y);
        if (result&2) psh_unequal(different, same, x);
        else psh_unequal(same, different, x);
    }
    if (unequal.size() == 1) {
        x = unequal.back(); unequal.pop_back(); 
        result = use_machine({(*same)[0], x[0]});

        if (result&1) psh_unequal(different, same, x);
        else psh_unequal(same, different, x);
    }

    return return_bigger();
}

l count_bigger(vector<l>* same) {
    l c = same->size();
    l result;
    vector<l> input;

    while (!positions.empty()) {
        input.clear();
        l last;
        for (int i = 0; i < same->size() && !positions.empty(); i++) {
            psh(&input, {(*same)[i], positions.back()});
            last = positions.back();
            positions.pop_back(); 
        }
        result = machine(input);
		if (result&1) {
            result++;
        } else {
            same->push_back(last);
        }
		c += (input.size()/2) - (result/2);
    }

    return c;
}

l subtask1() {
	l a, b;
	while (!positions.empty()) {
		a = positions.back(); positions.pop_back();
		b = machine({0, a});
		if (b == 0) cocaine.push_back(a);
		else flour.push_back(a);
	}

	return cocaine.size();
}

int count_mushrooms(int n) {
    cocaine.push_back(0);
    for (int i = 1; i < n; i++) positions.push_back(i);

    vector<l> test;
    for (int i = 0; i < n; i++) test.push_back(i);

    use_machine(test);

	mt19937_64 g;
	g.seed(267534);
	shuffle(positions.begin(), positions.end(), g);

    if (n < 200) return subtask1();

    auto [same, different] = get_amount_by_two(3);
    assert(uses <= 3);

    tie(same, different) = get_amount(threshold, same, different);
    
    
    l sol = count_bigger(same);


    if (*same == cocaine) return sol;
    else return n - sol;
}

• Subtask 1: 96.5812 / 100