QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666322#9178. All-You-Can-EatmaspyWA 32ms3824kbC++239.9kb2024-10-22 17:50:412024-10-22 17:50:46

Judging History

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

  • [2024-10-22 17:50:46]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:3824kb
  • [2024-10-22 17:50:41]
  • 提交

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

  auto drop = [&](vc<int> out) -> void {
    for (auto& x: out) ++x;
    print(len(out), out);
  };

  vc<pair<int, int>> dat;
  int now = 0;
  FOR(i, N) {
    INT(x);
    if (now >= 600) {
      print(0);
      print("IGNORE");
    }
    {
      sort(all(dat));
      reverse(all(dat));
      int greedy = x;
      vc<pair<int, int>> tmp;
      vc<int> out;
      for (auto& [y, j]: dat) {
        if (greedy + y > 1000) {
          out.eb(j);
        } else {
          greedy += y;
          tmp.eb(y, j);
        }
      }
      if (greedy >= 600) {
        now = greedy;
        swap(dat, tmp);
        drop(out);
        print("TAKE");
        dat.eb(x, i);
        continue;
      }
    }
    dat.eb(x, i);
    sort(all(dat));
    vc<pair<int, int>> tmp;
    vc<int> out;
    now = 0;
    for (auto& [y, j]: dat) {
      if (now + y > 1000) {
        out.eb(j);
      } else {
        now += y;
        tmp.eb(y, j);
      }
    }
    swap(dat, tmp);
    sort(all(out));
    if (len(out) && out.back() == i) {
      POP(out);
      drop(out);
      print("IGNORE");
    } else {
      drop(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: 3628kb

input:

1
5
10
13
450
585
465

output:

0 
TAKE
0 
TAKE
0 
TAKE
1 3
TAKE
0
IGNORE
1 4
TAKE

result:

ok OK, worst = 0.648188 (1 test case)

Test #2:

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

input:

1
1
100

output:

0 
TAKE

result:

ok OK, worst = 1.000000 (1 test case)

Test #3:

score: 0
Accepted
time: 32ms
memory: 3604kb

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: 20ms
memory: 3560kb

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: 6ms
memory: 3600kb

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: 9ms
memory: 3820kb

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

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: 27ms
memory: 3524kb

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: 0
Accepted
time: 1ms
memory: 3620kb

input:

1
2
2
999

output:

0 
TAKE
1 1
TAKE

result:

ok OK, worst = 1.000000 (1 test case)

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3624kb

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
...

result:

wrong answer alg = 599 opt = 1000 (test case 50)