結果

問題 No.2813 Cookie
ユーザー Pres1dentPres1dent
提出日時 2024-07-29 18:30:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 13,869 bytes
コンパイル時間 6,473 ms
コンパイル使用メモリ 307,628 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-29 18:30:15
合計ジャッジ時間 11,296 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
6,816 KB
testcase_01 AC 124 ms
6,816 KB
testcase_02 AC 104 ms
6,940 KB
testcase_03 AC 88 ms
6,940 KB
testcase_04 AC 93 ms
6,940 KB
testcase_05 AC 96 ms
6,940 KB
testcase_06 AC 88 ms
6,944 KB
testcase_07 AC 92 ms
6,940 KB
testcase_08 AC 87 ms
6,940 KB
testcase_09 AC 92 ms
6,940 KB
testcase_10 AC 146 ms
6,940 KB
testcase_11 AC 86 ms
6,940 KB
testcase_12 AC 87 ms
6,940 KB
testcase_13 AC 81 ms
6,940 KB
testcase_14 AC 84 ms
6,940 KB
testcase_15 AC 83 ms
6,940 KB
testcase_16 AC 84 ms
6,944 KB
testcase_17 AC 87 ms
6,940 KB
testcase_18 AC 81 ms
6,944 KB
testcase_19 AC 83 ms
6,944 KB
testcase_20 AC 84 ms
6,944 KB
testcase_21 AC 86 ms
6,940 KB
testcase_22 AC 84 ms
6,944 KB
testcase_23 AC 81 ms
6,944 KB
testcase_24 AC 82 ms
6,944 KB
testcase_25 AC 87 ms
6,940 KB
testcase_26 AC 72 ms
6,940 KB
testcase_27 AC 70 ms
6,940 KB
testcase_28 AC 72 ms
6,940 KB
testcase_29 AC 70 ms
6,940 KB
testcase_30 AC 72 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long int;
using lll = __int128;
using i64 = long long;
using i128 = __int128;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using piii = tuple<int, int, int>;
using piiii = tuple<int, int, int, int>;
using piiiii = tuple<int, int, int, int, int>;
using pll = pair<ll, ll>;
using plll = tuple<ll, ll, ll>;
using pllll = tuple<ll, ll, ll, ll>;
using plllll = tuple<ll, ll, ll, ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
// MACRO
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#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__))))
#define rep2(i, m, n) for (ll i = (m); i < (n); ++i) // [m, n)
#define rep(i, n) rep2(i, 0, n) // [0, n)
#define drep2(i, m, n) for (ll i = (n)-1; i >= (m); --i) // [m, n)
#define drep(i, n) drep2(i, 0, n) // [0, n)
#define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed)
#define zpad(i) cout << setfill('0') << setw(i)
#define dout cout << fixed << setprecision(10)
#define douts(i) cout << fixed << setprecision(i) << scientific
#define pcnt __builtin_popcountll
#define si(c) ((ll)(c).size())
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define SORT(v) sort(all(v))
#define REV(v) reverse(all(v))
#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())
#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 lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
#define bs(c, x) binary_search(all(c), (x))
// 入力
#define INT(...)                                                                                                                                               \
    int __VA_ARGS__;                                                                                                                                           \
    IN(__VA_ARGS__)
#define INTd(...)                                                                                                                                              \
    int __VA_ARGS__;                                                                                                                                           \
    IN2(__VA_ARGS__)
#define LL(...)                                                                                                                                                \
    ll __VA_ARGS__;                                                                                                                                            \
    IN(__VA_ARGS__)
#define LLd(...)                                                                                                                                               \
    ll __VA_ARGS__;                                                                                                                                            \
    IN2(__VA_ARGS__)
#define STR(...)                                                                                                                                               \
    string __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define CHR(...)                                                                                                                                               \
    char __VA_ARGS__;                                                                                                                                          \
    IN(__VA_ARGS__)
#define DBL(...)                                                                                                                                               \
    double __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define VEC(type, name, size)                                                                                                                                  \
    vector<type> name(size);                                                                                                                                   \
    IN(name)
#define VECd(type, name, size)                                                                                                                                 \
    vector<type> name(size);                                                                                                                                   \
    IN2(name)
#define VEC2(type, name1, name2, size)                                                                                                                         \
    vector<type> name1(size), name2(size);                                                                                                                     \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC2d(type, name1, name2, size)                                                                                                                        \
    vector<type> name1(size), name2(size);                                                                                                                     \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)                                                                                                                  \
    vector<type> name1(size), name2(size), name3(size);                                                                                                        \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VEC3d(type, name1, name2, name3, size)                                                                                                                 \
    vector<type> name1(size), name2(size), name3(size);                                                                                                        \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)                                                                                                           \
    vector<type> name1(size), name2(size), name3(size), name4(size);                                                                                           \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);
#define VEC4d(type, name1, name2, name3, name4, size)                                                                                                          \
    vector<type> name1(size), name2(size), name3(size), name4(size);                                                                                           \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w)                                                                                                                                   \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN(name)
#define VVd(type, name, h, w)                                                                                                                                  \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN2(name)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &);
template <class T> void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
void IN2() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
template <class Head, class... Tail> void IN2(Head &head, Tail &...tail) {
    scan(head);
    --head;
    IN2(tail...);
}
// 出力
void OUT() { cout << endl; }
template <class Head, class... Tail> void OUT(const Head &head, const Tail &...tail) {
    cout << head;
    if(sizeof...(tail)) cout << ' ';
    OUT(tail...);
}
template <class Ch, class Tr, class Container> std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, const Container &x) {
    bool f = true;
    if(&os == &cerr) os << "[";
    for(auto &y : x) {
        if(&os == &cerr)
            os << (f ? "" : ", ") << y;
        else
            os << (f ? "" : " ") << y;
        f = false;
    }
    if(&os == &cerr) os << "]";
    return os;
}
namespace yesno_impl {
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
const string firstsecond[2] = {"second", "first"};
const string FirstSecond[2] = {"Second", "First"};
const string possiblestr[2] = {"impossible", "possible"};
const string Possiblestr[2] = {"Impossible", "Possible"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
void first(bool t = 1) { cout << firstsecond[t] << endl; }
void First(bool t = 1) { cout << FirstSecond[t] << endl; }
void possible(bool t = 1) { cout << possiblestr[t] << endl; }
void Possible(bool t = 1) { cout << Possiblestr[t] << endl; }
}; // namespace yesno_impl
using namespace yesno_impl;
// デバッグ出力
#ifdef _PRES1DENT_DEBUG
  const string COLOR_RESET = "\033[0m";
  const string BRIGHT_GREEN = "\033[1;32m";
  const string BRIGHT_RED = "\033[1;31m";
  const string BRIGHT_CYAN = "\033[1;36m";
  const string NORMAL_CROSSED = "\033[0;9;37m";
  const string RED_BACKGROUND = "\033[1;41m";
  const string NORMAL_FAINT = "\033[0;2m";
  #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << COLOR_RESET << std::endl
  #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << COLOR_RESET << std::endl : std::cerr)
#else
  #define dbg(x) ((void)0)
  #define dbgif(cond, x) ((void)0)
#endif
struct fast_ios {
  fast_ios(){
    cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); };
} fast_ios_;
// CONST
constexpr int INF = numeric_limits<int>::max();
constexpr ll LNF= numeric_limits<ll>::max();
// 便利関数
ll max(int x, ll y) { return max((ll)x, y); }
ll max(ll x, int y) { return max(x, (ll)y); }
int min(int x, ll y) { return min((ll)x, y); }
int min(ll x, int y) { return min(x, (ll)y); }
template <typename T = ll, typename S> T SUM(const S &v) { return accumulate(all(v), T(0)); }
template <class T, class U> bool chmax(T &l, const U &r) { if (l < r) { l = r; return true; } return false; }
template <class T, class U> bool chmin(T &l, const U &r) { if (l > r) { l = r; return true; } return false; }

vector<int> di = { -1, 0, 1, 0 };
vector<int> dj = { 0, 1, 0, -1 };
ll my_pow(ll a, int x) { assert(x >= 0); ll ret = 1; rep(i, x) { assert(LNF / x > a); ret *= a; } return ret; }
bool kaibun(string s) { for (int i = 0; i < (int)s.size() / 2; i++) if (s[i] != s[s.size() - 1 - i])  return false; return true; }


vi expe() {
  int D = 50;
  vi grundy(D);
  rep2(d, 1, D) {
    vi g;
    g.pb(0);
    auto rec = [&](auto&& self, int rem, int lo, int cur) -> void {
      assert(rem >= 0);
      if (!rem) {
        g.pb(cur);
        return;
      }
      rep2(i, lo, rem + 1) {
        self(self, rem - i, i, cur ^ grundy.at(i));
      }
    };
    rec(rec, d, 1, 0);
    UNIQUE(g);
    int mex = 0;
    while (bs(g, mex)) mex++;
    grundy.at(d) = mex;
  }
  return grundy;
}

int main() {
  auto naive = expe();
  vi v = { 0, 1, 1, 2, 2, 4 ,4, 6 };
  vi v2 = { 0, 0, 2 };
  auto g = [&](int x) -> int {
    if (x < 8) return v[x];
    x -= 8;
    return (x / 3 + 2) * 4 + v2[x % 3];
  };
  int D = 50;
  vi fast;
  rep(i, D) {
    dbg(i);
    fast.eb(g(i));
  }
  dbg(naive);
  dbg(fast);
  assert(naive == fast);
  int t; cin >> t;
  rep(_, t) {
    int n; cin >> n;
    int sg = 0;
    rep(i, n) {
      INT(a);
      sg ^= g(a);
    }
    if (sg == 0) OUT("Bob");
    else OUT("Alice");
  }
}
0