QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#697603 | #9178. All-You-Can-Eat | ucup-team4975 | WA | 2ms | 3876kb | C++23 | 2.8kb | 2024-11-01 15:03:48 | 2024-11-01 15:03:49 |
Judging History
answer
#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el '\n'
#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif
#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif
#ifdef LOCAL
#define debugv(x) \
cerr << setw(4) << #x << ":: "; \
for (auto i : x) \
cerr << i << " "; \
cerr << endl
#else
#define debugv(x)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
out << x.fir << " " << x.sec << endl;
return out;
}
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
void solve()
{
int n, cnt = 0, flag = 0, sum = 0;
cin >> n;
vector<int> a(n + 1);
vector<int> vis(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (flag || a[i] > 1000) {
cout << "0\nIGNORE" << endl;
continue;
}
if (a[i] >= 600) {
cout << cnt << " ";
for (int j = 1; j < i; j++) {
if (vis[j] == 1)
cout << j << " ";
}
cout << endl;
cout << "TAKE" << endl;
vis[i] = 1, flag = 1, cnt = 1;
sum = a[i];
continue;
}
if (sum + a[i] > 1000) {
if (cnt == 1) {
int pl;
for (int j = 1; j < i; j++) {
if (vis[j] == 1) {
pl = j;
break;
}
}
if (a[pl] < a[i]) {
cout << "0\nIGNORE" << endl;
}
else {
cout << "1 " << pl << endl;
cout << "TAKE" << endl;
}
}
else {
assert(cnt >= 2);
flag = 1, vis[i] = 1;
vector<int> las(1010, 0), dp(1010, 0);
vector<int> ans;
dp[0] = 1;
for (int j = 1; j <= i; j++) {
if (vis[i] == 0)
continue;
for (int k = 1000 - a[j]; k >= 0; k--) {
if (!dp[k])
continue;
dp[k + a[j]] = 1;
las[k + a[j]] = j;
}
}
int st = 0;
for (int j = 1000; j >= 0; j--) {
if (dp[j] == 1) {
st = j;
break;
}
}
assert(st >= 600);
while (st) {
ans.push_back(las[st]);
st = st - a[las[st]];
}
for (auto x : ans) {
vis[x]++;
}
int tmp = 0;
assert(vis[i] == 2);
for (int j = 1; j <= i; j++) {
if (vis[j] == 1)
tmp++;
}
cout << tmp << " ";
for (int j = 1; j <= i; j++) {
if (vis[j] == 1)
cout << j << " ";
}
cout << "\nTAKE" << endl;
}
}
else if (sum + a[i] >= 600) {
sum += a[i];
vis[i] = 1;
flag = 1;
cnt++;
cout << "0\nTAKE" << endl;
}
else {
sum += a[i];
vis[i] = 1;
cnt++;
cout << "0\nTAKE" << endl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
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: 1ms
memory: 3584kb
input:
1 1 100
output:
0 TAKE
result:
ok OK, worst = 1.000000 (1 test case)
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3876kb
input:
2000 5 535 529 536 588 558 5 515 525 599 507 549 5 561 567 504 557
output:
0 TAKE 1 1 TAKE 0 IGNORE 0 IGNORE 0 IGNORE 0 TAKE 0 IGNORE 0 IGNORE 1 1 TAKE 0 IGNORE 0 TAKE 0 IGNORE 1 1 TAKE 1 1 TAKE
result:
wrong output format Unexpected end of file - int32 expected (test case 3)