結果
問題 |
No.3258 Xor Division Game
|
ユーザー |
|
提出日時 | 2025-09-06 08:15:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 751 ms / 2,000 ms |
コード長 | 1,945 bytes |
コンパイル時間 | 2,557 ms |
コンパイル使用メモリ | 207,376 KB |
実行使用メモリ | 245,616 KB |
最終ジャッジ日時 | 2025-09-06 08:16:17 |
合計ジャッジ時間 | 27,253 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> vector<T> zaatu(vector<T> &A){ //座標圧縮=Compress. vector<T> B = A; sort(B.begin(),B.end()); B.erase(unique(B.begin(),B.end()),B.end()); for(auto &a : A) a = lower_bound(B.begin(),B.end(),a)-B.begin(); return B; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int move = 0; auto dfs = [&](auto dfs,vector<int> &A) -> void { if(A.size() == 0) return; int m = zaatu(A).size(); vector<deque<int>> Q(m); int n = A.size(); for(int i=0; i<n; i++) Q[A.at(i)].push_back(i); queue<int> one; for(int i=0; i<m; i++) if(Q.at(i).size() == 1) one.push(i); int posl = 0,posr = n-1; while(one.size()){ auto v = one.front(); one.pop(); if(Q.at(v).size() == 0) continue; int sepa = Q[v].front(); Q.at(v).pop_front(); move++; int sl = sepa-posl,sr = posr-sepa; if(sl < sr){ vector<int> next; next.reserve(sl); for(int i=posl; i<sepa; i++){ next.push_back(A.at(i)); Q[A.at(i)].pop_front(); if(Q.at(A.at(i)).size() == 1) one.push(A.at(i)); } posl = sepa+1; dfs(dfs,next); } else{ vector<int> next; next.reserve(sr); for(int i=posr; i>sepa; i--){ next.push_back(A.at(i)); Q[A.at(i)].pop_back(); if(Q.at(A.at(i)).size() == 1) one.push(A.at(i)); } posr = sepa-1; dfs(dfs,next); } } }; int N; cin >> N; vector<int> A(N); for(auto &a : A) cin >> a; dfs(dfs,A); if(move%2) cout << "Alice\n"; else cout << "Bob\n"; }