QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773078#835. Easy Win5toubun_no_hanayomeWA 11ms12284kbC++142.2kb2024-11-23 00:38:232024-11-23 00:38:24

Judging History

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

  • [2024-11-23 00:38:24]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:12284kb
  • [2024-11-23 00:38:23]
  • 提交

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'