Submission #1058880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058880		c2zi6	Counting Mushrooms (IOI20_mushrooms)	C++14	98.69 / 100	5 ms	448 KiB

mushrooms

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "mushrooms.h"

VVI gp = {
    {-1, 1, 2, 6, 12, 20, 28, 34, 38, -1},
    {},
    {-1, -1, -1, 3, 4, -1, 5, -1, -1, -1},
    {},
    {},
    {},
    {-1, 7, -1, 8, 9, 10, 11, -1, -1, -1},
    {},
    {},
    {},
    {},
    {},
    {-1, 13, 14, 15, 16, 17, 18, 19, -1, -1},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {-1, 21, 22, 23, 24, 25, 26, 27, -1, -1},
    {},
    {},
    {},
    {},
    {},
    {},
    {},
    {-1, -1, -1, 29, 30, 31, 32, 33, -1, -1},
    {},
    {},
    {},
    {},
    {},
    {-1, -1, 35, -1, 36, 37, -1, -1, -1, -1},
    {},
    {},
    {},
    {}
};
vector<string> harc = {
    "A0B01C1DE",
    "00111",
    "001ABCD1E",
    "10111",
    "00110",
    "00100",
    "00A1BCD1E",
    "01111",
    "00011",
    "10110",
    "00101",
    "10100",
    "1A0B0C0DE",
    "00000",
    "10011",
    "00010",
    "10101",
    "01100",
    "11111",
    "01110",
    "1A0B0C0DE",
    "10000",
    "00001",
    "10010",
    "01011",
    "11100",
    "01101",
    "11110",
    "0AB1C10DE",
    "11101",
    "01000",
    "11011",
    "01010",
    "10001",
    "0011ABCDE",
    "11000",
    "11010",
    "01001",
    "11001"
};

const int LASTLIM = 135;

int count_mushrooms(int n) {
    VI mek, zro;
    zro.pb(0);
    int cnt0 = 1;
    int last = 1;
    auto ask = [&](string s, bool partial = false) {
        int m = 0;
        int z = 0;
        VI ret;
        int change = 0;
        for (char ch : s) {
            if (ch == '0') ret.pb(zro[z++]);
            else if (ch == '1') ret.pb(mek[m++]);
            else ret.pb(last++), change++;
        }
        last -= change;
        return use_machine(ret);
    };
    auto classify = [&](string s) {
        int j = 0;
        replr(i, last, last+s.size()-1) {
            if (s[j++] == '0') {
                zro.pb(i);
                cnt0++;
            } else {
                mek.pb(i);
            }
        }
        last += s.size();
    };
    auto expand = [&]() {
        int u = 0;
        while (true) {
            int ret = ask(harc[u], true);
            u = gp[u][ret];
            if (harc[u].size() == 5) {
                classify(harc[u]);
                break;
            }
        }
    };
    if (n >= 1000) {
        if (!ask("0x")) {
            classify("0");
        } else {
            classify("1");
            if (!ask("0x")) classify("0");
            else classify("1");
        }
        while (max(zro.size(), mek.size()) <= LASTLIM) {
            if (last+1 >= n) break;
            if (mek.size() >= zro.size()) {
                int ret = ask("1x1x");
                if (ret == 0)       classify("11");
                else if (ret == 1)  classify("10");
                else if (ret == 2)  classify("01");
                else                classify("00");
            } else {
                int ret = ask("0x0x");
                if (ret == 0)       classify("00");
                else if (ret == 1)  classify("01");
                else if (ret == 2)  classify("10");
                else                classify("11");
            }
            if (zro.size() >= 3 && mek.size() >= 2) break;
        }
        while (max(mek.size(), zro.size()) <= LASTLIM) expand();
    }
    while (last < n) {
        VI qr;
        for (int x : (mek.size() > zro.size() ? mek : zro)) {
            qr.pb(x);
            qr.pb(last++);
            if (last >= n) break;
        }
        int ret = use_machine(qr);
        int urish = (ret+1)/2;
        if (mek.size() > zro.size()) {
            cnt0 += urish;
            if (ret & 1) zro.pb(last-1);
            else mek.pb(last-1);
        } else {
            cnt0 += qr.size()/2 - urish;
            if (ret & 1) mek.pb(last-1);
            else zro.pb(last-1);
        }

        if (max(mek.size(), zro.size()) <= LASTLIM && zro.size() >= 3 && mek.size() >= 2 && n >= 1000) {
            while (max(mek.size(), zro.size()) <= LASTLIM) expand();
        }
    }
    return cnt0;
}

• Subtask 1: 98.69 / 100