結果

問題 No.670 log は定数
ユーザー mkawa2mkawa2
提出日時 2023-03-19 16:26:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,623 ms / 4,000 ms
コード長 991 bytes
コンパイル時間 692 ms
コンパイル使用メモリ 76,668 KB
実行使用メモリ 16,064 KB
最終ジャッジ日時 2023-10-18 17:51:33
合計ジャッジ時間 18,388 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,502 ms
16,064 KB
testcase_01 AC 1,538 ms
16,064 KB
testcase_02 AC 1,623 ms
16,064 KB
testcase_03 AC 1,563 ms
16,064 KB
testcase_04 AC 1,483 ms
16,064 KB
testcase_05 AC 1,518 ms
16,064 KB
testcase_06 AC 1,589 ms
16,064 KB
testcase_07 AC 1,595 ms
16,064 KB
testcase_08 AC 1,522 ms
16,064 KB
testcase_09 AC 1,460 ms
16,064 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:5:23: warning: left shift count >= width of type [-Wshift-count-overflow]
    5 | uint64_t mask = (1ull << 64) - 1ull;
      |                  ~~~~~^~~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

uint64_t mask = (1ull << 64) - 1ull;
uint64_t seed;

uint64_t value() {
    seed ^= (seed << 13);
    seed ^= (seed >> 7);
    seed ^= (seed << 17);
    return seed >> 33;
}

int main() {
    int n, q;
    cin >> n >> q >> seed;

    for (int i = 0; i < 10000; i++) {
        value();
    }

    const int m = 1 << 18;
    vector<vector<uint64_t>> aa(m);
    vector<uint64_t> cs(m + 1, 0);

    for (int i = 0; i < n; i++) {
        uint64_t a = value();
        uint64_t g = a >> 13;
        aa[g].push_back(a);
        cs[g + 1]++;
    }

    for (int i = 0; i < m; i++) {
        cs[i + 1] += cs[i];
    }

    uint64_t ans = 0;
    for (int i = 0; i < q; i++) {
        uint64_t x = value();
        uint64_t g = x >> 13;
        uint64_t s = 0;
        for (auto a : aa[g]) {
            if (a < x) {
                s++;
            }
        }
        ans ^= (s + cs[g]) * i;
    }

    cout << ans << endl;
    return 0;
}
0