QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#582643#9178. All-You-Can-Eatucup-team4435#RE 37ms3624kbC++207.8kb2024-09-22 17:03:322024-09-22 17:03:40

Judging History

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

  • [2024-09-22 17:03:40]
  • 评测
  • 测评结果:RE
  • 用时:37ms
  • 内存:3624kb
  • [2024-09-22 17:03:32]
  • 提交

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())

/*
 ! WARNING: MOD must be prime.
 ! WARNING: MOD must be less than 2^30.
 * Use .get() to get the stored value.
 */
template<uint32_t mod>
class montgomery {
    static_assert(mod < uint32_t(1) << 30, "mod < 2^30");
    using mint = montgomery<mod>;

private:
    uint32_t value;

    static constexpr uint32_t inv_neg_mod = []() {
        uint32_t x = mod;
        for (int i = 0; i < 4; ++i) {
            x *= uint32_t(2) - mod * x;
        }
        return -x;
    }();
    static_assert(mod * inv_neg_mod == -1);

    static constexpr uint32_t neg_mod = (-uint64_t(mod)) % mod;

    static uint32_t reduce(const uint64_t &value) {
        return (value + uint64_t(uint32_t(value) * inv_neg_mod) * mod) >> 32;
    }

    inline static const mint ONE = mint(1);

public:
    montgomery() : value(0) {}
    montgomery(const mint &x) : value(x.value) {}

    template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>>
    montgomery(const T &x) : value(!x ? 0 : reduce(int64_t(x % int32_t(mod) + int32_t(mod)) * neg_mod)) {}

    static constexpr uint32_t get_mod() {
        return mod;
    }

    uint32_t get() const {
        auto real_value = reduce(value);
        return real_value < mod ? real_value : real_value - mod;
    }

    template<typename T>
    mint power(T degree) const {
        degree = (degree % int32_t(mod - 1) + int32_t(mod - 1)) % int32_t(mod - 1);
        mint prod = 1, a = *this;
        for (; degree > 0; degree >>= 1, a *= a)
            if (degree & 1)
                prod *= a;

        return prod;
    }

    mint inv() const {
        return power(-1);
    }

    mint& operator=(const mint &x) {
        value = x.value;
        return *this;
    }

    mint& operator+=(const mint &x) {
        if (int32_t(value += x.value - (mod << 1)) < 0) {
            value += mod << 1;
        }
        return *this;
    }

    mint& operator-=(const mint &x) {
        if (int32_t(value -= x.value) < 0) {
            value += mod << 1;
        }
        return *this;
    }

    mint& operator*=(const mint &x) {
        value = reduce(uint64_t(value) * x.value);
        return *this;
    }

    mint& operator/=(const mint &x) {
        return *this *= x.inv();
    }

    friend mint operator+(const mint &x, const mint &y) {
        return mint(x) += y;
    }

    friend mint operator-(const mint &x, const mint &y) {
        return mint(x) -= y;
    }

    friend mint operator*(const mint &x, const mint &y) {
        return mint(x) *= y;
    }

    friend mint operator/(const mint &x, const mint &y) {
        return mint(x) /= y;
    }

    mint& operator++() {
        return *this += ONE;
    }

    mint& operator--() {
        return *this -= ONE;
    }

    mint operator++(int) {
        mint prev = *this;
        *this += ONE;
        return prev;
    }

    mint operator--(int) {
        mint prev = *this;
        *this -= ONE;
        return prev;
    }

    mint operator-() const {
        return mint(0) - *this;
    }

    bool operator==(const mint &x) const {
        return get() == x.get();
    }

    bool operator!=(const mint &x) const {
        return get() != x.get();
    }

    bool operator<(const mint &x) const {
        return get() < x.get();
    }

    template<typename T>
    explicit operator T() {
        return get();
    }

    friend std::istream& operator>>(std::istream &in, mint &x) {
        std::string s;
        in >> s;
        x = 0;
        bool neg = s[0] == '-';
        for (const auto c : s)
            if (c != '-')
                x = x * 10 + (c - '0');

        if (neg)
            x *= -1;

        return in;
    }

    friend std::ostream& operator<<(std::ostream &out, const mint &x) {
        return out << x.get();
    }

    static int32_t primitive_root() {
        if constexpr (mod == 1'000'000'007)
            return 5;
        if constexpr (mod == 998'244'353)
            return 3;
        if constexpr (mod == 786433)
            return 10;

        static int root = -1;
        if (root != -1)
            return root;

        std::vector<int> primes;
        int value = mod - 1;
        for (int i = 2; i * i <= value; i++)
            if (value % i == 0) {
                primes.push_back(i);
                while (value % i == 0)
                    value /= i;
            }

        if (value != 1)
            primes.push_back(value);

        for (int r = 2;; r++) {
            bool ok = true;
            for (auto p : primes)
                if ((mint(r).power((mod - 1) / p)).get() == 1) {
                    ok = false;
                    break;
                }

            if (ok)
                return root = r;
        }
    }
};

// constexpr uint32_t MOD = 1'000'000'007;
constexpr uint32_t MOD = 998'244'353;
using mint = montgomery<MOD>;

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<mint> 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].get() == 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].get() != 0) {
                        w -= x;
                        b.emplace_back(x, i);
                        continue;
                    }
                    update(x);
                }
                rem.push_back(i);
            }
            assert(w == 0);
            a = b;

            bool ignore = find(all(rem), id) != rem.end();
            if (ignore) {
                rem.erase(find(all(rem), id));
            }
            cout << len(rem);
            for (auto i : rem) {
                cout << ' ' << i;
            }
            cout << "\n" << (ignore ? "IGNORE" : "TAKE") << 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);
            a.erase(find(all(a), big[1]));
            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: 3504kb

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: 3564kb

input:

1
1
100

output:

0
TAKE

result:

ok OK, worst = 1.000000 (1 test case)

Test #3:

score: 0
Accepted
time: 25ms
memory: 3560kb

input:

2000
5
535
529
536
588
558
5
515
525
599
507
549
5
561
567
504
557
596
5
592
503
549
549
536
5
590
572
589
540
544
5
524
553
545
555
543
5
523
571
577
506
594
5
519
527
521
587
539
5
561
569
573
552
587
5
571
515
585
525
589
5
512
572
565
516
527
5
573
579
564
514
557
5
518
595
509
518
549
5
549
541...

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
0
IGNORE
0
IGNORE
0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
TAKE
1 1
TAKE
0
IGNORE
1 2
TAKE
0
IGNORE
0
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
TAKE
0
IGNORE
0
IGNORE
1 1
TAKE
0
IGNORE...

result:

ok OK, worst = 0.836394 (2000 test cases)

Test #4:

score: 0
Accepted
time: 18ms
memory: 3564kb

input:

500
20
535
529
536
588
558
515
525
599
507
549
561
567
504
557
596
592
503
549
549
536
20
590
572
589
540
544
524
553
545
555
543
523
571
577
506
594
519
527
521
587
539
20
561
569
573
552
587
571
515
585
525
589
512
572
565
516
527
573
579
564
514
557
20
518
595
509
518
549
549
541
580
535
531
540
...

output:

0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 2
TAKE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 9
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 13
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
TAKE
1 1
TAKE
0
IGNORE
1 2
TAKE
0
IGNORE
1 4
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
1 11
T...

result:

ok OK, worst = 0.836394 (500 test cases)

Test #5:

score: 0
Accepted
time: 34ms
memory: 3616kb

input:

200
50
535
529
536
588
558
515
525
599
507
549
561
567
504
557
596
592
503
549
549
536
590
572
589
540
544
524
553
545
555
543
523
571
577
506
594
519
527
521
587
539
561
569
573
552
587
571
515
585
525
589
50
512
572
565
516
527
573
579
564
514
557
518
595
509
518
549
549
541
580
535
531
540
596
51...

output:

0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 2
TAKE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 9
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 13
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IG...

result:

ok OK, worst = 0.836394 (200 test cases)

Test #6:

score: 0
Accepted
time: 17ms
memory: 3564kb

input:

100
100
535
529
536
588
558
515
525
599
507
549
561
567
504
557
596
592
503
549
549
536
590
572
589
540
544
524
553
545
555
543
523
571
577
506
594
519
527
521
587
539
561
569
573
552
587
571
515
585
525
589
512
572
565
516
527
573
579
564
514
557
518
595
509
518
549
549
541
580
535
531
540
596
516
...

output:

0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 2
TAKE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 9
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 13
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IG...

result:

ok OK, worst = 0.836394 (100 test cases)

Test #7:

score: 0
Accepted
time: 37ms
memory: 3564kb

input:

10
1000
535
529
536
588
558
515
525
599
507
549
561
567
504
557
596
592
503
549
549
536
590
572
589
540
544
524
553
545
555
543
523
571
577
506
594
519
527
521
587
539
561
569
573
552
587
571
515
585
525
589
512
572
565
516
527
573
579
564
514
557
518
595
509
518
549
549
541
580
535
531
540
596
516
...

output:

0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 2
TAKE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 9
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 13
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IG...

result:

ok OK, worst = 0.836394 (10 test cases)

Test #8:

score: 0
Accepted
time: 23ms
memory: 3508kb

input:

1
10000
535
529
536
588
558
515
525
599
507
549
561
567
504
557
596
592
503
549
549
536
590
572
589
540
544
524
553
545
555
543
523
571
577
506
594
519
527
521
587
539
561
569
573
552
587
571
515
585
525
589
512
572
565
516
527
573
579
564
514
557
518
595
509
518
549
549
541
580
535
531
540
596
516
...

output:

0
TAKE
1 1
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 2
TAKE
0
IGNORE
0
IGNORE
1 6
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 9
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
1 13
TAKE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IGNORE
0
IG...

result:

ok OK, worst = 0.836394 (1 test case)

Test #9:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

1
2
2
999

output:

0
TAKE
1 1
TAKE

result:

ok OK, worst = 1.000000 (1 test case)

Test #10:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

100
3
551
450
550
3
552
449
551
3
553
448
552
3
554
447
553
3
555
446
554
3
556
445
555
3
557
444
556
3
558
443
557
3
559
442
558
3
560
441
559
3
561
440
560
3
562
439
561
3
563
438
562
3
564
437
563
3
565
436
564
3
566
435
565
3
567
434
566
3
568
433
567
3
569
432
568
3
570
431
569
3
571
430
570
3
...

output:

0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0
TAKE
1 1
TAKE
0
TAKE
0...

result:

ok OK, worst = 0.600000 (100 test cases)

Test #11:

score: -100
Runtime Error

input:

41
238
1
0
0
4
1
2
0
5
0
5
1
5
2
3
5
1
1
5
5
2
1
3
4
1
5
0
4
1
5
3
1
4
4
1
1
4
2
2
1
0
4
1
5
1
2
4
3
4
0
2
2
0
3
3
4
2
2
1
2
0
3
5
3
3
1
2
4
3
3
3
0
3
1
1
0
4
5
4
1
3
5
2
0
1
0
2
3
0
5
4
5
5
5
1
5
5
5
2
1
4
0
0
4
3
2
5
0
4
1
1
5
3
5
2
3
1
3
3
0
2
3
1
2
3
5
0
5
2
3
5
3
0
3
4
1
0
1
3
1
2
0
4
5
4
3
0
4...

output:

0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE
0
TAKE...

result: