結果
問題 |
No.3258 Xor Division Game
|
ユーザー |
![]() |
提出日時 | 2025-09-05 19:05:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 273 ms / 2,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 3,443 ms |
コンパイル使用メモリ | 286,320 KB |
実行使用メモリ | 23,496 KB |
最終ジャッジ日時 | 2025-09-05 21:16:08 |
合計ジャッジ時間 | 18,374 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long #define all(x) (x).begin(), (x).end() //座標圧縮を行う関数 template<class T> vector<int> compress(vector<T> A) { int N = (int)A.size(); vector<T> B = A; sort(B.begin(), B.end()); vector<int> ret(N); rep(i, 0, N) { ret[i] = lower_bound(all(B), A[i]) - B.begin(); } return ret; } int N; vector<int> A; vector<vector<int>> pos; int count(int x, int l, int r) { return lower_bound(all(pos[x]), r) - lower_bound(all(pos[x]), l); } int f(int l, int r) { int m = -1; for (int i = 0; ; i++) { int left = l + i, right = r - i - 1; if (left > right) break; if (count(A[left], l, r) == 1) { m = left; break; } if (count(A[right], l, r) == 1) { m = right; break; } } if (m == -1) return r - l; return f(l, m) + f(m+1, r); } int main() { cin >> N; vector<int> F(N); rep(i, 0, N) cin >> F[i]; A = compress(F); pos.resize(N); rep(i, 0, N) { pos[A[i]].push_back(i); } int turn = N - f(0, N); // cout << "turn = " << turn << endl; cout << (turn%2? "Alice" : "Bob") << endl; }