結果
| 問題 | No.2813 Cookie |
| ユーザー |
 Pres1dent
|
| 提出日時 | 2024-07-29 18:34:19 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 97 ms / 2,000 ms |
| コード長 | 13,870 bytes |
| コンパイル時間 | 6,495 ms |
| コンパイル使用メモリ | 305,884 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-29 18:34:30 |
| 合計ジャッジ時間 | 10,841 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 70 ms
6,812 KB |
| testcase_01 | AC | 82 ms
6,816 KB |
| testcase_02 | AC | 85 ms
6,944 KB |
| testcase_03 | AC | 82 ms
6,944 KB |
| testcase_04 | AC | 97 ms
6,944 KB |
| testcase_05 | AC | 92 ms
6,940 KB |
| testcase_06 | AC | 87 ms
6,940 KB |
| testcase_07 | AC | 89 ms
6,940 KB |
| testcase_08 | AC | 86 ms
6,940 KB |
| testcase_09 | AC | 91 ms
6,940 KB |
| testcase_10 | AC | 89 ms
6,940 KB |
| testcase_11 | AC | 82 ms
6,944 KB |
| testcase_12 | AC | 80 ms
6,944 KB |
| testcase_13 | AC | 83 ms
6,940 KB |
| testcase_14 | AC | 84 ms
6,944 KB |
| testcase_15 | AC | 81 ms
6,944 KB |
| testcase_16 | AC | 88 ms
6,944 KB |
| testcase_17 | AC | 82 ms
6,944 KB |
| testcase_18 | AC | 79 ms
6,944 KB |
| testcase_19 | AC | 80 ms
6,940 KB |
| testcase_20 | AC | 81 ms
6,940 KB |
| testcase_21 | AC | 84 ms
6,940 KB |
| testcase_22 | AC | 83 ms
6,940 KB |
| testcase_23 | AC | 80 ms
6,940 KB |
| testcase_24 | AC | 83 ms
6,940 KB |
| testcase_25 | AC | 81 ms
6,944 KB |
| testcase_26 | AC | 71 ms
6,940 KB |
| testcase_27 | AC | 68 ms
6,940 KB |
| testcase_28 | AC | 72 ms
6,940 KB |
| testcase_29 | AC | 73 ms
6,944 KB |
| testcase_30 | AC | 68 ms
6,940 KB |
ソースコード
#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");
}
}