QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#697679#9178. All-You-Can-Eatucup-team4975ML 0ms0kbC++232.9kb2024-11-01 15:19:082024-11-01 15:19:09

Judging History

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

  • [2024-11-01 15:19:09]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-11-01 15:19:08]
  • 提交

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

result: