結果
問題 | No.670 log は定数 |
ユーザー |
![]() |
提出日時 | 2018-03-23 22:44:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,787 ms / 4,000 ms |
コード長 | 1,847 bytes |
コンパイル時間 | 1,003 ms |
コンパイル使用メモリ | 95,956 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 21:58:26 |
合計ジャッジ時間 | 21,112 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <cstdio>#include <cassert>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <map>#include <set>#include <functional>#include <stack>#include <queue>#include <tuple>#define getchar getchar_unlocked#define putchar putchar_unlocked#define _rep(_1, _2, _3, _4, name, ...) name#define rep2(i, n) rep3(i, 0, n)#define rep3(i, a, b) rep4(i, a, b, 1)#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)using namespace std;using i64 = long long;using u8 = unsigned char;using u32 = unsigned;using u64 = unsigned long long;using f80 = long double;int get_int() {int n, c, sign = 0;while ((c = getchar()) < '-');if (c == '-') sign = 1, n = 0;else n = c - '0';while ((c = getchar()) >= '0') n = n * 10 + c - '0';return sign ? -n : n;}u64 seed;int next() {seed = seed ^ (seed << 13);seed = seed ^ (seed >> 7);seed = seed ^ (seed << 17);return (seed >> 33);}void solve() {int N, Q;while (~scanf("%d %d %llu", &N, &Q, &seed)) {rep(i, 1e4) next();vector<int> a(N);rep(i, N) a[i] = next();sort(a.begin(), a.end());int shift = 16, b = 1 << shift;vector<int> ofs(b + 1);int o = 0;for (int i = 0; i < b; ++i) {while (o < N && (a[o] >> shift) <= i) ++o;ofs[i + 1] = o;}int *p = a.data();i64 ans = 0;for (int qi = 0; qi < Q; ++qi) {int x = next();int b = x >> shift;int res = lower_bound(p + ofs[b], p + ofs[b + 1], x) - p;ans ^= i64(res) * qi;}printf("%lld\n", ans);}}int main() {clock_t beg = clock();solve();clock_t end = clock();fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);return 0;}