QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#582484#9178. All-You-Can-Eatucup-team4435#RE 1ms3648kbC++202.6kb2024-09-22 16:37:092024-09-22 16:37:11

Judging History

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

  • [2024-09-22 16:37:11]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3648kb
  • [2024-09-22 16:37:09]
  • 提交

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

result: