結果
問題 | No.670 log は定数 |
ユーザー | merom686 |
提出日時 | 2018-03-23 23:41:14 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,966 ms / 4,000 ms |
コード長 | 2,072 bytes |
コンパイル時間 | 2,159 ms |
コンパイル使用メモリ | 85,904 KB |
実行使用メモリ | 395,164 KB |
最終ジャッジ日時 | 2023-09-07 04:25:57 |
合計ジャッジ時間 | 27,653 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
外部呼び出し有り |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,890 ms
395,004 KB |
testcase_01 | AC | 2,913 ms
395,008 KB |
testcase_02 | AC | 2,948 ms
395,012 KB |
testcase_03 | AC | 2,900 ms
394,896 KB |
testcase_04 | AC | 2,886 ms
394,940 KB |
testcase_05 | AC | 2,966 ms
395,080 KB |
testcase_06 | AC | 2,926 ms
395,012 KB |
testcase_07 | AC | 2,953 ms
395,164 KB |
testcase_08 | AC | 2,901 ms
394,944 KB |
testcase_09 | AC | 2,906 ms
395,004 KB |
ソースコード
#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); } pair<int, int> *pii; 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 = 2; size_t n = last - first; T *p[2] = { &*first, pii }; 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]); } } 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; //} int q2 = q / 2; pii = (pair<int, int> *)std::malloc(q2 * sizeof(pair<int, int>)); vector<pair<int, int>> x(q2); for (int l = 0; l < 2; l++) { for (int h = 0; h < q2; h++) { x[h] = { next(), h + l * q2 }; } radix_sort(x.begin(), x.end()); ll k = 0; for (int h = 0; h < q2; h++) { while (k < n && a[k] < x[h].first) k++; r ^= k * x[h].second; } } cout << r << endl; return 0; }