QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#666299 | #9178. All-You-Can-Eat | maspy | WA | 36ms | 3848kb | C++23 | 9.4kb | 2024-10-22 17:39:37 | 2024-10-22 17:39:47 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io2.hpp"
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
long double __VA_ARGS__; \
IN(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void read(int &a) { cin >> a; }
void read(long long &a) { cin >> a; }
void read(char &a) { cin >> a; }
void read(double &a) { cin >> a; }
void read(long double &a) { cin >> a; }
void read(string &a) { cin >> a; }
template <class T, class S>
void read(pair<T, S> &p) {
read(p.first), read(p.second);
}
template <class T>
void read(vector<T> &a) {
for (auto &i: a) read(i);
}
template <class T>
void read(T &a) {
cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
read(head);
IN(tail...);
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
os << A.fi << " " << A.se;
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
for (size_t i = 0; i < A.size(); i++) {
if (i) os << " ";
os << A[i];
}
return os;
}
// chatgpt helped me
class CoutInitializer {
public:
CoutInitializer() { std::cout << std::fixed << std::setprecision(15); }
};
static CoutInitializer cout_initializer;
void print() {
cout << "\n";
cout.flush();
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
cout << head;
if (sizeof...(Tail)) cout << " ";
print(forward<Tail>(tail)...);
}
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
void solve() {
INT(N);
vc<pair<int, int>> dat;
int now = 0;
FOR(i, N) {
INT(x);
if (now >= 600) {
print(0);
print("IGNORE");
}
dat.eb(x, i);
sort(all(dat));
now = 0;
vc<pair<int, int>> tmp;
vc<int> out;
for (auto& [x, i]: dat) {
if (now + x > 1000) {
out.eb(i);
} else {
now += x;
tmp.eb(x, i);
}
}
swap(dat, tmp);
if (len(out) && out.back() == i) {
POP(out);
for (auto& x: out) ++x;
print(len(out), out);
print("IGNORE");
} else {
for (auto& x: out) ++x;
print(len(out), out);
print("TAKE");
}
}
}
signed main() {
INT(T);
FOR(T) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3476kb
input:
1 5 10 13 450 585 465
output:
0 TAKE 0 TAKE 0 TAKE 0 IGNORE 0 TAKE
result:
ok OK, worst = 1.000000 (1 test case)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
1 1 100
output:
0 TAKE
result:
ok OK, worst = 1.000000 (1 test case)
Test #3:
score: 0
Accepted
time: 35ms
memory: 3848kb
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 ...
result:
ok OK, worst = 0.836394 (2000 test cases)
Test #4:
score: 0
Accepted
time: 12ms
memory: 3500kb
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 ...
result:
ok OK, worst = 0.836394 (500 test cases)
Test #5:
score: 0
Accepted
time: 36ms
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 IGN...
result:
ok OK, worst = 0.836394 (200 test cases)
Test #6:
score: 0
Accepted
time: 32ms
memory: 3496kb
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 IGN...
result:
ok OK, worst = 0.836394 (100 test cases)
Test #7:
score: 0
Accepted
time: 16ms
memory: 3612kb
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 IGN...
result:
ok OK, worst = 0.836394 (10 test cases)
Test #8:
score: 0
Accepted
time: 11ms
memory: 3548kb
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 IGN...
result:
ok OK, worst = 0.836394 (1 test case)
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3804kb
input:
1 2 2 999
output:
0 TAKE 0 IGNORE
result:
wrong answer alg = 2 opt = 999 (test case 1)