結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2018-03-24 00:11:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,585 ms / 4,000 ms |
コード長 | 1,230 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 74,184 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-06-25 00:31:33 |
合計ジャッジ時間 | 29,971 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>using namespace std;using Int = long long;//INSERT ABOVE HEREusing ull = unsigned long long;ull seed;Int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return (seed >> 33);}constexpr signed N = 2e5;constexpr signed Q = 5e7;constexpr signed W = 1e5;constexpr signed B = 17;signed a[N];ull xx[W],yy[W];ull *x=xx,*y=yy;constexpr ull ms=(1LL<<B)-1;constexpr signed SZ = max(1<<B, W);signed c[SZ];inline void rsort(Int e){memset(c,0,sizeof(c));for(signed i=0;i<W;i++) c[(x[i]>>e)&ms]++;for(signed i=1;i<SZ;i++) c[i]+=c[i-1];for(signed i=W-1;i>=0;i--){y[c[(x[i]>>e)&ms]-1]=x[i];c[(x[i]>>e)&ms]--;}swap(x,y);}signed main() {Int n, q;cin >> n >> q >> seed;for (signed i = 0; i < 10000; i++) next();for (signed i = 0; i < N; i++) a[i] = next();sort(a,a+N);Int ans=0;for(signed i=0;i<Q;i+=W){for(signed j=0;j<W;j++) x[j]=(next()<<B)|j;rsort(0);rsort(B);rsort(B+B);for(signed j=0,cnt=0;j<W;j++){cnt = lower_bound(a+cnt,a+N,(x[j]>>B))-a;ans ^= (i+(x[j]&ms)) * cnt;}}cout<<ans<<endl;}