oj.uz

Submission #1058890

# Submission time Handle Problem Language Result Execution time Memory
1058890 2024-08-14T14:48:58 Z c2zi6 Counting Mushrooms (IOI20_mushrooms) C++14
100 / 100
 5 ms 600 KB 
#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 = 115;

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 3 ms 456 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 3 ms 456 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 2 ms 452 KB Output is correct
19 Correct 4 ms 344 KB Output is correct
20 Correct 3 ms 452 KB Output is correct
21 Correct 3 ms 600 KB Output is correct
22 Correct 3 ms 344 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Correct 3 ms 344 KB Output is correct
28 Correct 3 ms 344 KB Output is correct
29 Correct 3 ms 452 KB Output is correct
30 Correct 3 ms 344 KB Output is correct
31 Correct 3 ms 344 KB Output is correct
32 Correct 4 ms 600 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 3 ms 344 KB Output is correct
35 Correct 5 ms 344 KB Output is correct
36 Correct 3 ms 344 KB Output is correct
37 Correct 3 ms 344 KB Output is correct
38 Correct 4 ms 344 KB Output is correct
39 Correct 3 ms 344 KB Output is correct
40 Correct 5 ms 344 KB Output is correct
41 Correct 3 ms 344 KB Output is correct
42 Correct 3 ms 344 KB Output is correct
43 Correct 3 ms 344 KB Output is correct
44 Correct 3 ms 344 KB Output is correct
45 Correct 3 ms 344 KB Output is correct
46 Correct 5 ms 456 KB Output is correct
47 Correct 3 ms 344 KB Output is correct
48 Correct 3 ms 344 KB Output is correct
49 Correct 3 ms 344 KB Output is correct
50 Correct 3 ms 344 KB Output is correct
51 Correct 3 ms 512 KB Output is correct
52 Correct 5 ms 448 KB Output is correct
53 Correct 3 ms 344 KB Output is correct
54 Correct 3 ms 452 KB Output is correct
55 Correct 3 ms 344 KB Output is correct
56 Correct 3 ms 344 KB Output is correct
57 Correct 3 ms 344 KB Output is correct
58 Correct 3 ms 344 KB Output is correct
59 Correct 3 ms 344 KB Output is correct
60 Correct 3 ms 344 KB Output is correct
61 Correct 3 ms 344 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 1 ms 344 KB Output is correct
64 Correct 0 ms 596 KB Output is correct
65 Correct 0 ms 344 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 0 ms 344 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 344 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 0 ms 344 KB Output is correct
74 Correct 0 ms 344 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 1 ms 344 KB Output is correct
77 Correct 0 ms 344 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 0 ms 344 KB Output is correct
80 Correct 0 ms 344 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 1 ms 344 KB Output is correct
83 Correct 0 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 0 ms 344 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 0 ms 344 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 0 ms 344 KB Output is correct