結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2018-03-23 23:27:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,049 bytes |
コンパイル時間 | 949 ms |
コンパイル使用メモリ | 86,004 KB |
実行使用メモリ | 801,024 KB |
最終ジャッジ日時 | 2024-06-24 22:56:05 |
合計ジャッジ時間 | 11,514 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | MLE * 1 -- * 9 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <functional>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;using ull = unsigned long long;ull seed;int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return (seed >> 33);}template <class I>void radix_sort(I first, I last) {using T = typename std::iterator_traits<I>::value_type;constexpr int L = 16, M = 1 << L, K = (sizeof(T) * 8 + L - 1) / L;size_t n = last - first;T *p[2] = { &*first, (T *)std::malloc(n * sizeof(T)) };size_t m[M];for (int k = 0; k < K; k++) {std::fill_n(m, M, 0);for (size_t i = 0; i < n; i++) {m[(p[0][i].first >> (L * k) & M - 1)]++;}for (int j = M - 1; j > 0; j--) {m[j] = m[j - 1];}m[0] = 0;for (int j = 2; j < M; j++) {m[j] += m[j - 1];}for (size_t i = 0; i < n; i++) {T t = p[0][i];p[1][m[t.first >> (L * k) & M - 1]++] = t;}std::swap(p[0], p[1]);}std::free(p[1]);}int 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());ll r = 0;//for (int h = 0; h < q; h++) {// int x = next();// auto it = lower_bound(a.begin(), a.end(), x);// ll k = it - a.begin();// r ^= k * h;//}vector<pair<int, int>> x(q / 2);for (int l = 0; l < 2; l++) {for (int h = 0; h < q / 2; h++) {x[h] = { next(), h + l * (q / 2) };}radix_sort(x.begin(), x.end());ll k = 0;for (int h = 0; h < q / 2; h++) {while (k < n && a[k] < x[h].first) k++;r ^= k * x[h].second;}}cout << r << endl;return 0;}