QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405821#6370. Slot Machinejames1BadCreeperWA 1ms3568kbC++202.4kb2024-05-06 14:06:172024-05-06 14:06:18

Judging History

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

  • [2024-05-06 14:06:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3568kb
  • [2024-05-06 14:06:17]
  • 提交

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); 
			// cerr << i << " " << res << " " << adv << "\n"; 
            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: 1ms
memory: 3568kb

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:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'