QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214094 | #3449. Pizza Problems | ucup-team1209 | WA | 1ms | 4292kb | C++20 | 1.3kb | 2023-10-14 17:12:10 | 2023-10-14 17:12:11 |
Judging History
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';
}
}
Details
Tip: Click on the bar to expand more detailed information
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