QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405817 | #6370. Slot Machine | james1BadCreeper | WA | 2ms | 3612kb | C++20 | 2.0kb | 2024-05-06 14:01:42 | 2024-05-06 14:01:42 |
Judging History
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) {
ios::sync_with_stdio(0);
int T = 1; cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3612kb
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
output:
2 3 2 2 2 2 2
result:
wrong answer Output contains longer sequence [length = 7], but answer contains 1 elements