結果
問題 | No.670 log は定数 |
ユーザー | ei1333333 |
提出日時 | 2018-03-23 23:50:43 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,812 bytes |
コンパイル時間 | 3,233 ms |
コンパイル使用メモリ | 209,200 KB |
実行使用メモリ | 9,156 KB |
最終ジャッジ日時 | 2023-09-07 04:45:46 |
合計ジャッジ時間 | 47,876 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3,954 ms
8,424 KB |
testcase_01 | AC | 3,924 ms
8,264 KB |
testcase_02 | AC | 3,949 ms
8,776 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 3,975 ms
9,000 KB |
testcase_05 | AC | 3,950 ms
8,684 KB |
testcase_06 | AC | 3,959 ms
8,780 KB |
testcase_07 | AC | 3,915 ms
8,748 KB |
testcase_08 | AC | 3,913 ms
8,412 KB |
testcase_09 | AC | 3,928 ms
9,156 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; template< typename T > struct RadixHeap { using uint = unsigned; vector< pair< uint, T > > v[32]; uint size, last; RadixHeap() : size(0), last(0) {} bool empty() const { return size == 0; } inline int getbit(uint a) { return a ? 32 - __builtin_clz(a) : 0; } void push(uint key, const T &value) { ++size; v[getbit(key ^ last)].emplace_back(key, value); } pair< uint, T > pop() { if(v[0].empty()) { int idx = 1; while(v[idx].empty()) ++idx; last = min_element(begin(v[idx]), end(v[idx]))->first; for(auto &p : v[idx]) v[getbit(p.first ^ last)].emplace_back(p); v[idx].clear(); } --size; auto ret = v[0].back(); v[0].pop_back(); return ret; } }; ull seed; inline int next() { seed = seed ^ (seed << 13); seed = seed ^ (seed >> 7); seed = seed ^ (seed << 17); return (seed >> 33); } 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(begin(a), end(a)); a.push_back(INT_MAX); ll sm = 0; RadixHeap< int > rad; int last = 0; for (int i = 0; i < q; i++) { if(i - last >= 500000) { int ptr = 0; for(int j = last; j < i; j++) { auto p = rad.pop(); while(a[ptr] < p.first) ++ptr; sm ^= ll(ptr) * p.second; } last = i; rad.last = 0; } rad.push(next(), i); } int ptr = 0; for(int j = last; j < q; j++) { auto p = rad.pop(); while(a[ptr] < p.first) ++ptr; sm ^= ll(ptr) * p.second; } rad.last = 0; cout << sm << endl; }