QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214094#3449. Pizza Problemsucup-team1209WA 1ms4292kbC++201.3kb2023-10-14 17:12:102023-10-14 17:12:11

Judging History

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

  • [2023-10-14 17:12:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4292kb
  • [2023-10-14 17:12:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std::ranges;
using std::cin, std::cout;
const int N = 10000;
std::vector<int> a[N], b[N];
std::map<std::string, int> map;
std::string li[N];
int s[N];
int cc;
std::mt19937 gen;
int get(std::string s) {
	if(map.count(s)) return map[s];
	li[++cc] = s;
	return map[s] = cc;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	for(int i = 0;i < n;++i) {
		int m; cin >> m;
		for(int j = 0;j < m;++j) {
			std::string t; cin >> t;
			if(t[0] == '+') {
				t.erase(t.begin()), a[i].push_back(get(t));
			} else {
				t.erase(t.begin()), b[i].push_back(get(t));
			}
		}
	}
	for(int i = 1;i <= cc;++i) {
		s[i] = gen() % 2;
	}
	for(;;) {
		int bad = 0;
		for(int i = 0;i < n;++i) {
			int c = 0;
			for(int x : a[i]) c += s[x];
			for(int x : b[i]) c += !s[x];
			if(c * 3 >= a[i].size() + b[i].size()) {
				continue;
			}
			static std::vector<int> p; p.clear();
			for(int x : a[i]) if(!s[x]) p.push_back(x);
			for(int x : b[i]) if(s[x]) p.push_back(x);
			shuffle(p.begin(), p.end(), gen);
			for(int i = 0;(i + c) * 3 < (int) a[i].size() + b[i].size();++i) {
				s[p[i]] ^= 1;
			}
			bad = 1;
		}
		if(!bad) break;
	}
	for(int i = 1;i <= cc;++i) if(s[i]) {
		cout << li[i] << '\n';
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4292kb

input:

1
4 +zucchini +mozzarella +mushrooms -artichoke

output:

zucchini
mozzarella
artichoke

result:

ok 

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 4284kb

input:

3
3 +redbeans +soylentgreen -bluecheese
3 +redbeans -soylentgreen +bluecheese
3 -redbeans +soylentgreen +bluecheese

output:


result:

wrong answer Friend 1/3 only has 1 of 3 wishes satisfied