QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405816 | #6370. Slot Machine | james1BadCreeper | RE | 0ms | 0kb | C++20 | 2.1kb | 2024-05-06 14:01:27 | 2024-05-06 14:01:28 |
answer
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 1e5 + 5;
int n, L[N];
vector<pair<int, int>> a[N];
vector<int> lck[N];
// map<int, int> st[N];
int solve(int ax) {
int len = 0;
map<int, int> mp;
for (int i = 0; i < n; ++i) if (ax >> i & 1) {
len += L[i + 1];
for (auto [x, y] : a[i + 1]) mp[x] += y;
}
vector<pair<int, int>> arr;
for (auto [x, y] : mp) arr.emplace_back(x, y);
return arr.size() == len ? INF : arr.size() + 1;
}
int solve2(int ax, int i) {
int len = 0;
map<int, int> mp;
len += L[i + 1];
for (auto [x, y] : a[i + 1]) mp[x] += y;
vector<pair<int, int>> arr;
for (auto [x, y] : mp) arr.emplace_back(x, y);
return arr.size() == len ? INF : arr.size() + 1;
}
void solve(void) {
cin >> n;
for (int i = 1; i < N; ++i) lck[i].clear();
for (int i = 1; i <= n; ++i) {
a[i].clear(); cin >> L[i];
int m = L[i];
map<int, int> mp;
while (m--) {
int x; cin >> x;
++mp[x];
}
for (auto [x, y] : mp) a[i].emplace_back(x, y), lck[x].push_back(i);
}
int ans = 1e9;
for (int i = 0; i < n; ++i) ans = min(ans, solve2(1 << i, i));
if (n <= 3) {
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans = min(ans, solve((1 << i) | (1 << j)));
}
if (n >= 3) {
multiset<int> ss;
for (int i = 1; i <= n; ++i)
for (auto it : a[i]) ss.insert(it.first);
for (int i = 1; i <= n; ++i) {
int res = 0, adv = 0;
for (auto it : a[i]) ss.erase(ss.find(it.first));
for (auto it : a[i])
if (ss.find(it.first) == ss.end()) ++adv;
else {
int ret = 1e9;
for (int j : lck[it.first]) if (i != j)
ret = min(ret, int(a[j].size()));
res = max(res, ret);
}
ans = min(ans, res + adv + 1);
for (auto it : a[i]) ss.insert(it.first);
}
}
cout << ans << "\n";
}
int main(void) {
freopen("slot.in", "r", stdin);
freopen("slot.out", "w", stdout);
ios::sync_with_stdio(0);
int T = 1; cin >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
7 4 1 2 3 4 1 1 1 2 1 3 1 4 7 4 7 4 4 7 7 4 1 5