結果
問題 | 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; }