QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773076 | #835. Easy Win | 5toubun_no_hanayome | WA | 14ms | 12256kb | C++14 | 2.2kb | 2024-11-23 00:37:16 | 2024-11-23 00:37:18 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;
const int N = 5e5 + 5;
bool pre[N], f[__lg(N) + 1][N];
bool mt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
int n;
cin >> n;
rep(i, 1, n) {
int a;
cin >> a;
pre[a] ^= 1;
}
rep(i, 1, n)
pre[i] ^= pre[i - 1];
int k = __lg(n);
rep(i, 0, k) {
per(j, n, 1)
f[i][j] = (j + (1 << i + 1) <= n ? f[i][j + (1 << i + 1)] : 0) ^ pre[min(j + (1 << i + 1) - 1, n)] ^ pre[min(j + (1 << i) - 1, n)];
}
rep(i, 1, n) {
bool ans = 0;
rep(j, 0, k) {
for(int k = 0;k <= n;k += i + 1) {
int len = min(i + 1, n - k + 1);
int l = (len >> j + 1) << j + 1;
ans ^= f[j][k] ^ f[j][k + l] ^ pre[min(k + l + (1 << j + 1) - 1, k + len - 1)] ^ pre[min(k + l + (1 << j) - 1, k + len - 1)];
}
if(ans)
break;
}
cout << (ans ? "Alice" : "Bob") << " \n"[i == n];
}
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5960kb
input:
6 6 6 6 6 6 6
output:
Bob Bob Bob Bob Bob Bob
result:
ok 6 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
4 1 2 3 4
output:
Bob Alice Bob Alice
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
5 1 2 3 2 2
output:
Bob Alice Bob Bob Bob
result:
ok 5 tokens
Test #4:
score: -100
Wrong Answer
time: 14ms
memory: 12256kb
input:
50000 1 2 1 2 1 5 1 4 5 3 10 6 6 13 1 1 17 15 2 18 6 3 11 17 21 12 13 7 20 28 10 17 1 7 11 31 30 10 22 14 32 25 21 2 15 20 3 4 13 9 28 41 17 52 15 33 9 46 53 33 2 28 55 17 50 10 24 3 61 26 47 19 8 47 29 29 44 16 11 34 42 56 65 82 34 35 35 83 46 29 9 25 48 71 9 93 79 59 82 99 88 101 19 43 92 53 20 3 ...
output:
Bob Bob Bob Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Al...
result:
wrong answer 1st words differ - expected: 'Alice', found: 'Bob'