QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740511#7940. Impossible Numbersucup-team3215RE 2ms3932kbC++234.9kb2024-11-13 10:14:492024-11-13 10:14:49

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 10:14:49]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3932kb
  • [2024-11-13 10:14:49]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
constexpr int K = 10;
constexpr int nax = 1 << K;

struct GenNumber {
    int n;
    vector<int> now;
    array<int, K> cnt{};

    GenNumber() = default;

    GenNumber(const GenNumber &) = default;

    GenNumber(int n, array<int, K> cnt) : n(n), now(n), cnt(cnt) {
        now[0] = 1;
    }

    vector<int> get() {
        vector<int> res;
        gen(0, res);
        return res;
    }

    bool gen(int pos, vector<int> &v) {
        if (pos == n) {
            return true;
        }
        for (; now[pos] < K; ++now[pos]) {
            if (cnt[now[pos]]) {
                --cnt[now[pos]];
                v.push_back(now[pos]);
                auto ans = gen(pos + 1, v);
                ++cnt[now[pos]];
                if (pos + 1 == n)++now[pos];
                if (ans)return true;
                else v.pop_back();
            }
        }
        now[pos] = 0;
        return false;
    }
};

vector<int> mn(array<int, K> cnt) {
    int n = accumulate(cnt.begin(), cnt.end(), 0);
    vector<int> res;
    auto gen = [&](auto &&gen, int pos) -> void {
        if (pos == n) {
            return;
        }
        for (int i = pos == 0; i < K; ++i) {
            if (cnt[i]) {
                --cnt[i];
                res.push_back(i);
                gen(gen, pos + 1);
            }
        }
    };
    gen(gen, 0);
    return res;
}

struct GenDistribution {
    int n;
    int last{-1};
    array<int, K> now{};
    array<char, K> ok;
    array<char, K> uninit;

    GenDistribution(int n, array<char, K> ok) : n(n), ok(ok) {
        int first = find(ok.begin(), ok.end(), 1) - ok.begin();
        now[first] = n;
        for (int i = 0; i < K; ++i)if (ok[i])last = i;
    }

    array<int, K> get() {
        fill(uninit.begin(), uninit.end(), 0);
        array<int, K> res{};
        gen(0, n, res);
        return res;
    }

    bool gen(int pos, int s, array<int, K> &v) {
        if (pos == K) {
            return !s;
        }
        if (uninit[pos])now[pos] = ok[pos] ? s : 0;
        for (; now[pos] >= (pos == last ? s : 0); --now[pos]) {
            v[pos] = now[pos];
            auto ans = gen(pos + 1, s - now[pos], v);
            if (pos + 1 == K)--now[pos];
            if (ans)return true;
            v[pos] = 0;
        }
        uninit[pos] = 1;
        return false;
    }
};


int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 6; ++j) {
            int x;
            cin >> x;
            a[i] |= 1 << x;
        }
    }
    vector<GenDistribution> g;
    for (int mask = 0; mask < nax; ++mask) {
        int num = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] & mask)++num;
        }
        ++num;
        array<char, K> ok{};
        for (int j = 0; j < K; ++j)ok[j] = (mask >> j) & 1;
        g.emplace_back(num, ok);
    }
    auto cmp = [&](const vector<int> &lhs, const vector<int> &rhs) {
        return lhs.size() < rhs.size() || lhs.size() == rhs.size() && lhs < rhs ? true : false;
    };
    auto cmpf = [&](const pair<array<int, K>, int> &lhs, const pair<array<int, K>, int> &rhs) {
        return lhs.first != rhs.first ? cmp(mn(lhs.first), mn(rhs.first)) : lhs.second < rhs.second;
    };
    set<pair<array<int, K>, int>, decltype(cmpf)> s(cmpf);
    for (int i = 0; i < nax; ++i) {
        auto t = g[i].get();
        if (mn(t).empty()){
            auto nxt = g[i].get();
            if(mn(nxt).empty())continue;
            t = nxt;
        }
        s.insert({t, i});
    }
    map<array<int, K>, GenNumber> gn;
    auto cmpg = [&](const pair<vector<int>, array<int, K>> &lhs, const pair<vector<int>, array<int, K>> &rhs) {
        return lhs.first != rhs.first ? cmp(lhs.first, rhs.first) : lhs.second < rhs.second;
    };
    set<pair<vector<int>, array<int, K>>, decltype(cmpg)> best(cmpg);
    while (k--) {
        while (1) {
            auto it = *s.begin();
            s.erase(it);
            for (int i = 0; i < K; ++i) {
                auto x = it.first;
                x[i]++;
                s.insert({x, -1});
            }
            auto nxt = g[it.second].get();
            if (accumulate(nxt.begin(), nxt.end(), 0))s.insert({nxt, it.second});
            if (!gn.count(it.first)){
                int n = accumulate(it.first.begin(), it.first.end(), 0);
                gn[it.first] = GenNumber(n, it.first);
                best.insert({gn[it.first].get(), it.first});
                break;
            }
        }
        auto [val, who] = *best.begin();
        best.erase(*best.begin());
        auto nxt = gn[who].get();
        if (nxt.size())best.insert({nxt, who});
        for (auto x: val)cout << x;
        cout << " ";
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3932kb

input:

2 3
1 8 7 0 6 2
1 2 5 4 9 3

output:

33 34 35 

result:

ok single line: '33 34 35 '

Test #2:

score: -100
Runtime Error

input:

1 10
1 5 2 2 6 4

output:


result: