結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
|
提出日時 | 2024-12-25 05:34:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 3,000 ms |
コード長 | 1,477 bytes |
コンパイル時間 | 935 ms |
コンパイル使用メモリ | 80,828 KB |
実行使用メモリ | 99,736 KB |
最終ジャッジ日時 | 2024-12-25 05:34:23 |
合計ジャッジ時間 | 7,514 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
コンパイルメッセージ
main.cpp: In function 'void solve2(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >, long int, int)': main.cpp:21:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 21 | auto[al,ar]=A[i]; | ^ main.cpp:22:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 22 | auto[bl,br]=B[i]; | ^ main.cpp: In function 'void solve(std::vector<std::pair<int, int> >, long int, int)': main.cpp:45:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 45 | for(auto[l,r]:LR)if(l<r) | ^
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; int A[2<<17]; int ans=0; int mid(int l,int r,int k) { int m=l; while(m<r&&!(A[m]>>k&1))m++; return m; } void solve2(vector<pair<int,int> >A,vector<pair<int,int> >B,long K,int k) { if(k==-1)return; vector<pair<int,int> >zero,one; long v=0; for(int i=0;i<A.size();i++) { auto[al,ar]=A[i]; auto[bl,br]=B[i]; if(al==ar||bl==br)continue; int am=mid(al,ar,k),bm=mid(bl,br,k); zero.push_back(make_pair(al,am)); one.push_back(make_pair(bl,bm)); zero.push_back(make_pair(am,ar)); one.push_back(make_pair(bm,br)); v+=(long)(am-al)*(bm-bl); v+=(long)(ar-am)*(br-bm); } if(v>=K)solve2(zero,one,K,k-1); else { ans|=1<<k; for(int i=0;i<zero.size();i+=2)swap(one[i],one[i+1]); solve2(zero,one,K-v,k-1); } } void solve(vector<pair<int,int> >LR,long K,int k) { if(k==-1)return; vector<pair<int,int> >zero,one; long v=0; for(auto[l,r]:LR)if(l<r) { int m=mid(l,r,k); zero.push_back(make_pair(l,m)); one.push_back(make_pair(m,r)); v+=(long)(m-l)*(m-l-1)/2; v+=(long)(r-m)*(r-m-1)/2; } if(v<K) { ans|=1<<k; solve2(zero,one,K-v,k-1); } else { for(auto v:one)zero.push_back(v); solve(zero,K,k-1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; long K; cin>>N>>K; for(int i=0;i<N;i++)cin>>A[i]; sort(A,A+N); vector<pair<int,int> >fst; fst.push_back(make_pair(0,N)); solve(fst,K,29); cout<<ans<<endl; }