QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#697679 | #9178. All-You-Can-Eat | ucup-team4975 | ML | 0ms | 0kb | C++23 | 2.9kb | 2024-11-01 15:19:08 | 2024-11-01 15:19:09 |
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 || a[i] == 0) {
cout << "0\nIGNORE" << endl;
continue;
}
if (a[i] >= 600) {
cout << cnt << " ";
for (int j = 1; j < i; j++) {
if (vis[j] == 1) {
vis[j] = 0;
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;
vis[pl] = 0, vis[i] = 1, sum = a[i];
cout << "TAKE" << endl;
}
}
else {
assert(cnt >= 2);
flag = 1, vis[i] = 1;
vector<int> las(1010, 0), dp(1010, 0);
vector<int> ans;
dp[a[i]] = 1;
for (int j = 1; j < i; j++) {
if (vis[j] == 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 - a[i]);
while (st) {
ans.push_back(las[st]);
st = st - a[las[st]];
}
for (auto x : ans) {
vis[x]++;
}
int tmp = 0;
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: 0
Memory Limit Exceeded
input:
1 5 10 13 450 585
output:
0 TAKE 0 TAKE 0 TAKE