QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582643 | #9178. All-You-Can-Eat | ucup-team4435# | RE | 37ms | 3624kb | C++20 | 7.8kb | 2024-09-22 17:03:32 | 2024-09-22 17:03:40 |
Judging History
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...