QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#740511 | #7940. Impossible Numbers | ucup-team3215 | RE | 2ms | 3932kb | C++23 | 4.9kb | 2024-11-13 10:14:49 | 2024-11-13 10:14:49 |
Judging History
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