QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582484 | #9178. All-You-Can-Eat | ucup-team4435# | RE | 1ms | 3648kb | C++20 | 2.6kb | 2024-09-22 16:37:09 | 2024-09-22 16:37:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define len(a) int((a).size())
void solve(int /* test_num */) {
int n;
cin >> n;
vector<pair<int, int>> a;
bool got = false;
for (int id = 1; id <= n; id++) {
int val;
cin >> val;
if (got) {
cout << "0\nIGNORE" << endl;
continue;
}
a.emplace_back(val, id);
constexpr int N = 1000;
vector<int> ways(N + 1);
ways[0] = 1;
auto update = [&](int x) {
for (int i = N; i >= x; i--) {
ways[i] += ways[i - x];
}
};
auto roll_back = [&](int x) {
for (int i = x; i <= N; i++) {
ways[i] -= ways[i - x];
}
};
for (auto [x, id] : a) {
update(x);
}
int w = N;
while (ways[w] == 0) {
w--;
}
if (w >= 600) {
got = true;
vector<int> rem;
vector<pair<int, int>> b;
for (auto [x, i] : a) {
if (x <= w) {
roll_back(x);
if (ways[w - x] > 0) {
w -= x;
b.emplace_back(x, i);
} else {
update(x);
rem.push_back(i);
}
}
}
a = b;
cout << len(rem);
for (auto i : rem) {
cout << ' ' << i;
}
cout << "\nTAKE" << endl;
continue;
}
vector<pair<int, int>> big;
for (auto [x, i] : a) {
if (x >= 400) {
big.emplace_back(x, i);
}
}
sort(all(big));
assert(len(big) <= 2);
if (len(big) == 2) {
assert(big[0].second == id || big[1].second == id);
if (big[1].second == id) {
cout << "0\nIGNORE" << endl;
} else {
cout << "1 " << big[1].second << "\nTAKE" << endl;
}
} else {
int sum = 0;
for (auto [x, i] : a) {
sum += x;
}
assert(sum <= N);
cout << "0\nTAKE" << endl;
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
for (int test_num = 1; test_num <= tests; test_num++) {
solve(test_num);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
input:
1 5 10 13 450 585 465
output:
0 TAKE 0 TAKE 0 TAKE 1 3 TAKE 0 IGNORE
result:
ok OK, worst = 0.648188 (1 test case)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 100
output:
0 TAKE
result:
ok OK, worst = 1.000000 (1 test case)
Test #3:
score: -100
Runtime Error
input:
2000 5 535 529 536
output:
0 TAKE 1 1 TAKE