QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405816#6370. Slot Machinejames1BadCreeperRE 0ms0kbC++202.1kb2024-05-06 14:01:272024-05-06 14:01:28

Judging History

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

  • [2024-05-06 14:01:28]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-06 14:01:27]
  • 提交

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

output:


result: