結果
問題 | No.670 log は定数 |
ユーザー |
|
提出日時 | 2018-04-04 23:57:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,313 ms / 4,000 ms |
コード長 | 889 bytes |
コンパイル時間 | 2,241 ms |
コンパイル使用メモリ | 199,208 KB |
最終ジャッジ日時 | 2025-01-05 09:55:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;uint64_t SEED;int next() {SEED ^= SEED << 13;SEED ^= SEED >> 7;SEED ^= SEED << 17;return SEED >> 33;}const int BS = 1 << 16;const int BC = 1 << 15;int tot[BC], stot[BC + 1];vector<int> vals[BC];signed main() {int N, Q;cin >> N >> Q >> SEED;for (int i = 0; i < 10000; ++i) next();vector<int> A(N);for (int i = 0; i < N; ++i) A[i] = next();sort(A.begin(), A.end());for (int i = 0; i < N; ++i) {++tot[A[i] / BS];vals[A[i] / BS].emplace_back(A[i]);}for (int i = 0; i < BC; ++i) {stot[i + 1] = stot[i] + tot[i];}int64_t ans = 0;for (int i = 0; i < Q; ++i) {int x = next();int cnt = stot[x / BS];cnt += lower_bound(vals[x / BS].begin(), vals[x / BS].end(), x) - vals[x / BS].begin();ans ^= 1LL * cnt * i;}cout << ans << endl;return 0;}