제출 #1197343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197343		dong_gas	버섯 세기 (IOI20_mushrooms)	C++20	99.12 / 100	3 ms	460 KiB

mushrooms

#include <bits/extc++.h>
using namespace std;
int use_machine(vector<int> x);

int small(int n) {
    int b = 0;
    for (int i = 1; i + 1 < n; i += 2) b += use_machine({i, 0, i + 1});
    if ((n & 1) == 0) b += use_machine({0, n - 1});
    return n - b;
}

// sqrt(20000) = 141.xx
vector<int> a[2] = {{0}, {}};
int idx = 1, k = 79;


// rule: https://oj.uz/submission/303279 model code 참고...
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"}};

// map<vector<int>, string> prec1 = {{{}, "A0B0C0D1E"},  {{1}, "0D"},        {{2}, "0A0D0E"}, {{3}, "0A1BC0E0D"},
//                                   {{4}, "0A0E0BC1D"}, {{5}, "0A0BC1E0D"}, {{6}, "0A0D0E"}, {{7}, "0D"}};
// map<vector<int>, string> prec2 = {{{}, "0ABCDE"},    {{1}, "0ABCD"},   {{1, 1}, "AB0C"}, {{2}, "A0BCD"},
//                                   {{2, 1}, "AB0CE"}, {{2, 2}, "ABDC"}, {{2, 3}, "0C"},   {{3}, "A0BCE"},
//                                   {{3, 1}, "0B"},    {{3, 2}, "0BDC"}, {{3, 3}, "0D"},   {{3, 4}, "0D"},
//                                   {{4}, "A0BCD"},    {{4, 2}, "0C"},   {{4, 3}, "0ABCD"}};

int chk(string s, int state) {
    string t = s;
    int ret = 0;
    for (char& c: t) {
        if ('A' <= c && c <= 'Z') c = (char) ('0' + ((state) >> (c - 'A') & 1));
    }
    for (int i = 1; i < t.size(); i++) ret += (t[i - 1] != t[i]);
    return ret;
}

int count_mushrooms(int n) {
    // if (n <= 450) return small(n);
    int ret = 1;
    while (idx < n) {
        int t = a[0].size() < a[1].size();
        if (n - idx < 5 || a[t].size() >= k) {
            vector<int> query, &c = a[t];
            int qcnt = 0;
            // for (auto x: c) cout << x << ' ';
            // cout << "gdgdg\n";
            for (int i = 0; i < c.size() && idx < n; i++) query.push_back(c[i]), query.push_back(idx++), qcnt++;
            // for (auto qq: query) cout << qq << ' ';
            // cout << endl;
            // cout << query.size() << endl;

            int cnt = use_machine(query);
            int p = (cnt + 1) / 2;
            if (!t) p = qcnt - p;
            ret += p;
            if (cnt & 1) a[t ^ 1].push_back(idx - 1);
            else a[t].push_back(idx - 1);
            // cout << p << ' ' << ret << endl;
        }
        else {  // 다 쳐넣음
            map<vector<int>, string>& rule = (a[t].size() >= 3 && a[t ^ 1].size() >= 1) ? prec1 : prec2;
            vector<int> record, valid(32, 1);
            while (rule.count(record)) {
                string tmp = rule[record];
                // cout << "hi"<< rule[record] << endl;
                vector<int> query, cnt(2, 0);
                for (char c: tmp) {
                    if (c == '0' || c == '1') query.push_back(a[(c - '0') ^ t][cnt[(c - '0') ^ t]++]);
                    else query.push_back(idx + (c - 'A'));
                }
                // cout << tmp << endl;
                // for (auto qq: query) cout << qq << ' ';
                // cout << endl;
                int q = use_machine(query);
                // cout << q << ' ' << "chkquery\n";
                record.push_back(q);
                for (int state = 0; state < 32; state++) {
                    if (chk(tmp, state) != q) valid[state] = 0;
                }

            }
            // cout<<"rsz: "<<record.size()<<endl;
            // cout<<record[0]<<endl;

            for (int state = 0; state < 32; state++) {
                if (valid[state]) {
                    // cout<<"state = "<<state<<endl;
                    for (int i = 0; i < 5; i++) {
                        a[(state >> i & 1) ^ t].push_back(idx + i);
                        ret += (((state >> i & 1) ^ t) == 0);
                    }
                    // cout<<"a[0]: ";
                    // for (int x:a[0]) cout<<x<<' ';
                    // cout<<endl;
                    // cout<<"a[1]: ";
                    // for (int x:a[1]) cout<<x<<' ';
                    // cout<<endl;
                    idx += 5;
                    break;
                }
            }
        }
    }
    return ret;
}

• Subtask 1: 99.1228 / 100