結果
問題 |
No.3258 Xor Division Game
|
ユーザー |
|
提出日時 | 2025-09-06 08:07:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,020 bytes |
コンパイル時間 | 2,471 ms |
コンパイル使用メモリ | 213,584 KB |
実行使用メモリ | 263,924 KB |
最終ジャッジ日時 | 2025-09-06 08:08:25 |
合計ジャッジ時間 | 53,148 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 RE * 32 TLE * 4 -- * 1 |
ソースコード
#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(); map<int,deque<int>> Q; int n = A.size(); vector<int> C(m); for(int i=0; i<n; i++){ C.at(A.at(i))++; Q[A.at(i)].push_back(i); } queue<int> one; for(int i=0; i<m; i++) if(C.at(i) == 1) one.push(i); int posl = 0,posr = n-1; while(one.size()){ auto v = one.front(); one.pop(); if(C.at(v) == 0) continue; int sepa = Q[v].front(); Q.erase(Q.find(v)); 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)); C.at(A.at(i))--; Q[A.at(i)].pop_front(); if(C.at(A.at(i)) == 1) one.push(A.at(i)); } posl = sepa+1; dfs(dfs,next); } else{ vector<int> next; next.reserve(sr); for(int i=sepa+1; i<=posr; i++){ next.push_back(A.at(i)); C.at(A.at(i))--; Q[A.at(i)].pop_front(); if(C.at(A.at(i)) == 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"; }