結果
問題 | No.2740 Old Maid |
ユーザー |
![]() |
提出日時 | 2024-04-20 10:38:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 2,001 bytes |
コンパイル時間 | 3,435 ms |
コンパイル使用メモリ | 261,932 KB |
実行使用メモリ | 18,116 KB |
最終ジャッジ日時 | 2024-10-12 06:13:03 |
合計ジャッジ時間 | 11,892 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; template <class T> using V=vector<T>; template <class T> using VV=V<V<T>>; //B(n,V<int>(n)) template<typename T> struct BIT{ private: vector<T> A; const int n; public: BIT(int _n) : A(_n+1,0), n(_n){} T sum(int i){ i++; T s=0; while(i>0){ s+=A[i]; i-=i&-i; } return s; } T sum(int i,int j){ return sum(j)-sum(i-1); } void add(int i,T x){ i++; while(i<=n){ A[i]+=x; i+=i&-i; } } void update(int i,T x){ T tmp=sum(i,i); if(tmp!=x) add(i,x-tmp); } int lower_bound(T w){ if(w<=0) return 0; if(sum(n-1)<w) return n; int x=0,r=1; while(r<n) r=r<<1; for(int len=r;len>0;len=len>>1){ if(x+len<n && A[x+len]<w){ w-=A[x+len]; x+=len; } } return x; } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin>>n; V<int> P(n); map<int,int> m; rep(i,n){ cin>>P[i]; m[P[i]]=i; } BIT<ll> bit(n); rep(i,n) bit.add(i,1); V<int> used(n+1); priority_queue<int, vector<int>, greater<int> > que; rep(i,n) que.push(i+1); V<int> ANS; rep(i,n/2){ while(used[que.top()]) que.pop(); int p=que.top(); int a=bit.sum(m[p]); if(a==n-2*i){ que.pop(); while(used[que.top()]) que.pop(); int q=que.top(); que.pop(); int b=bit.sum(m[q]); int r=bit.lower_bound(b+1); ANS.push_back(q); ANS.push_back(P[r]); used[q]=1; used[P[r]]=1; bit.add(m[q],-1); bit.add(r,-1); que.push(p); } else{ int r=bit.lower_bound(a+1); ANS.push_back(p); ANS.push_back(P[r]); used[p]=1; used[P[r]]=1; bit.add(m[p],-1); bit.add(r,-1); que.pop(); } } rep(i,n){ if(i) cout<<" "; cout<<ANS[i]; } cout<<endl; return 0; }