QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773078 | #835. Easy Win | 5toubun_no_hanayome | WA | 11ms | 12284kb | C++14 | 2.2kb | 2024-11-23 00:38:23 | 2024-11-23 00:38:24 |
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) - 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)] ^ pre[min(k + l + (1 << j) - 1, k + len)];
}
if(ans)
break;
}
cout << (ans ? "Alice" : "Bob") << " \n"[i == n];
}
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6040kb
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: 0ms
memory: 3992kb
input:
4 1 2 3 4
output:
Bob Alice Bob Alice
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 1 2 3 2 2
output:
Bob Alice Bob Bob Bob
result:
ok 5 tokens
Test #4:
score: -100
Wrong Answer
time: 11ms
memory: 12284kb
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:
Alice Bob Alice Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice 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 Al...
result:
wrong answer 2nd words differ - expected: 'Alice', found: 'Bob'