제출 #1265008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265008		AksLolCoding	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	3 ms	524 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

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; }

std::vector<int> labels;
std::vector<std::vector<int>> lst;
int K = 110;

int ans;

void label(int p, int z) {
    labels[p] = z;
    lst[z].push_back(p);
    if (!z) ++ans;
}

int p;
int z;
vector<int> 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 std::string &s) {
    int ret = 0;
    for (int i = 0; i < (int)s.size() - 1; ++i) ret += int(s[i] != s[i + 1]);
    return ret;
}

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

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

map<vector<int>, 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<vector<int>, string> &m) {
    toQ.clear();
    for (int i = 0; i < 5; ++i) toQ.push_back(p + i);
    std::vector<int> seq;
    std::map<std::string, int> res;
    while (m.count(seq)) {
        std::string s = m[seq];
        int x = query(s);
        res[s] = x;
        seq.push_back(x);
    }
    std::vector<int> goodM;
    for (int mask = 0; mask < 32; ++mask) {
        bool ok = true;
        for (auto w: res) ok &= eval(subs(w.first, mask)) == w.second;
        if (ok) goodM.push_back(mask);
    }
    assert(goodM.size() == 1);
    int mask = goodM[0];
    for (int i = 0; i < 5; ++i) label(p++, ((mask >> i) & 1) ^ z);
}

int count_mushrooms(int n) {
    labels = std::vector<int>(n, -1);
    lst = std::vector<std::vector<int>>(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) {
            std::vector<int> m;
            int i = 0;
            while (p < n && i < (int)lst[z].size()) {
                m.push_back(p++);
                m.push_back(lst[z][i++]);
            }
            int x = use_machine(m);
            lst[z ^ (x & 1)].push_back(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 / 100