oj.uz

Submission #1087508

# Submission time Handle Problem Language Result Execution time Memory
1087508 2024-09-12T19:07:00 Z M4mou Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 6 ms 776 KB 
/*
 * Model solution for task mushrooms
 *
 * Author: Mikhail Tikhomirov
 */

#include "mushrooms.h"
#include <vector>
#include <string>
#include <map>
#include <cassert>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

vi labels;
vvi lst;
int K = 110;

int ans;

void label(int p, int z) {
//    cerr << p << ' ' << z << '\n';
    labels[p] = z;
    lst[z].pb(p);
    if (!z) ++ans;
}

int p;
int z;
vi toQ;

string subs(string s, int mask) {
    for (char &c: s) if (c >= 'A' && c <= 'Z') c = (char)('0' + ((mask >> (c - 'A')) & 1));
    return s;
}

int eval(const string &s) {
    int ret = 0;
    forn(i, (int)s.size() - 1) ret += int(s[i] != s[i + 1]);
    return ret;
}

int query(string s) {
    vi v;
    vi ptr(2);
    for (char c: s) {
        if (c == '0' || c == '1') {
            int d = (c - '0') ^ z;
            assert(ptr[d] < (int)lst[d].size());
            v.pb(lst[d][ptr[d]++]);
        } else {
            int l = c - 'A';
            v.pb(toQ[l]);
        }
    }
    return use_machine(v);
}

map<vi, string> prec1 = {
    {{}, "A0B0C0DE"},
    {{1}, "CED"},
    {{2}, "DBE0A"},
    {{3}, "CB0E0DA1"},
    {{4}, "D0A0E0CB1"},
    {{5}, "DBCE1"},
    {{6}, "CED"}
};

map<vi, string> prec2 = {
    {{}, "ABCDE0"},
    {{1}, "B0"},
    {{1, 1}, "EADC"},
    {{2}, "CB0D"},
    {{2, 1}, "EADB"},
    {{2, 2}, "DAE0CB"},
    {{3}, "CB0D"},
    {{3, 1}, "EDB0"},
    {{3, 2}, "AED"},
    {{3, 3}, "ED"},
    {{4}, "B0"},
    {{4, 1}, "0EACD"}
};


void magic(map<vi, string> &m) {
    toQ.clear();
    forn(i, 5) toQ.pb(p + i);
    vi seq;
    map<string, int> res;
    while (m.count(seq)) {
        string s = m[seq];
        int x = query(s);
        res[s] = x;
        seq.pb(x);
    }
    vi goodM;
    forn(mask, 32) {
        bool ok = true;
        for (auto w: res) ok &= eval(subs(w.fi, mask)) == w.se;
        if (ok) goodM.pb(mask);
    }
    assert(goodM.size() == 1);
    int mask = goodM[0];
    forn(i, 5) label(p++, ((mask >> i) & 1) ^ z);
}

int count_mushrooms(int n) {
    labels = vi(n, -1);
    lst = vvi(2);
    p = 1;
    ans = 0;
    label(0, 0);
    while (p < n) {
        z = lst[0].size() > lst[1].size() ? 0 : 1;
        if (n - p < 5 || (int)lst[z].size() >= K) {
            vi m;
            int i = 0;
            while (p < n && i < (int)lst[z].size()) {
                m.pb(p++);
                m.pb(lst[z][i++]);
            }
            int x = use_machine(m);
            lst[z ^ (x & 1)].pb(m[0]);
            x = (x + 1) / 2;
            ans += (z ? x : i - x);
        } else magic(!lst[z ^ 1].empty() && lst[z].size() >= 3 ? prec1 : prec2);
    }
    return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 516 KB Output is correct
14 Correct 2 ms 484 KB Output is correct
15 Correct 3 ms 516 KB Output is correct
16 Correct 4 ms 528 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 3 ms 344 KB Output is correct
19 Correct 3 ms 344 KB Output is correct
20 Correct 4 ms 520 KB Output is correct
21 Correct 4 ms 776 KB Output is correct
22 Correct 4 ms 344 KB Output is correct
23 Correct 3 ms 344 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 3 ms 344 KB Output is correct
26 Correct 3 ms 600 KB Output is correct
27 Correct 3 ms 344 KB Output is correct
28 Correct 3 ms 344 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 3 ms 516 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 3 ms 600 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 5 ms 524 KB Output is correct
35 Correct 3 ms 608 KB Output is correct
36 Correct 3 ms 344 KB Output is correct
37 Correct 4 ms 516 KB Output is correct
38 Correct 3 ms 344 KB Output is correct
39 Correct 4 ms 344 KB Output is correct
40 Correct 3 ms 528 KB Output is correct
41 Correct 3 ms 340 KB Output is correct
42 Correct 5 ms 344 KB Output is correct
43 Correct 3 ms 344 KB Output is correct
44 Correct 4 ms 344 KB Output is correct
45 Correct 3 ms 344 KB Output is correct
46 Correct 4 ms 524 KB Output is correct
47 Correct 3 ms 344 KB Output is correct
48 Correct 5 ms 516 KB Output is correct
49 Correct 4 ms 344 KB Output is correct
50 Correct 3 ms 344 KB Output is correct
51 Correct 4 ms 528 KB Output is correct
52 Correct 6 ms 344 KB Output is correct
53 Correct 3 ms 344 KB Output is correct
54 Correct 6 ms 520 KB Output is correct
55 Correct 3 ms 344 KB Output is correct
56 Correct 5 ms 344 KB Output is correct
57 Correct 4 ms 344 KB Output is correct
58 Correct 6 ms 524 KB Output is correct
59 Correct 4 ms 596 KB Output is correct
60 Correct 4 ms 600 KB Output is correct
61 Correct 3 ms 516 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 344 KB Output is correct
64 Correct 0 ms 344 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 0 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 0 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 1 ms 344 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 0 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