#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
uint32_t xorshift32(uint32_t x) {
x ^= x << 13;
x ^= x >> 17;
return x ^= x << 5;
}
using namespace std;
const int n = (1<<20);
const int block_size = 16;
alignas(64) int a[n], b[n * 2];
int eytzinger(int i = 0, int k = 1) {
if (k <= n) {
i = eytzinger(i, 2 * k);
b[k] = a[i++];
i = eytzinger(i, 2 * k + 1);
}
return i;
}
int search(int x) {
int k = 1;
while (k <= n) {
__builtin_prefetch(b + k * block_size);
k = 2 * k + (b[k] < x);
}
return k - n + 1;
}
int main() {
std::cout << std::fixed << std::setprecision(3);
for (int i = 0; i < n; i++) {
a[i] = i;
}
eytzinger();
{
double tin = (double)clock();
uint32_t x = 1, check = 0;
for (int i = 0; i < (1 << 20); i++) {
x = xorshift32(x);
check ^= search(x % n);
}
double tout = (double)clock();
std::cout << "eytzinger = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
}
{
double tin = (double)clock();
uint32_t x = 1, check = 0;
for (int i = 0; i < (1 << 20); i++) {
x = xorshift32(x);
check ^= int(std::lower_bound(a, a + n, x % n) - a);
}
double tout = (double)clock();
std::cout << "lower_bound = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
}
return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1aW50MzJfdCB4b3JzaGlmdDMyKHVpbnQzMl90IHgpIHsKCXggXj0geCA8PCAxMzsKCXggXj0geCA+PiAxNzsKCXJldHVybiB4IF49IHggPDwgNTsKfQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBuID0gKDE8PDIwKTsKY29uc3QgaW50IGJsb2NrX3NpemUgPSAxNjsKYWxpZ25hcyg2NCkgaW50IGFbbl0sIGJbbiAqIDJdOwoKaW50IGV5dHppbmdlcihpbnQgaSA9IDAsIGludCBrID0gMSkgewogICAgaWYgKGsgPD0gbikgewogICAgICAgIGkgPSBleXR6aW5nZXIoaSwgMiAqIGspOwogICAgICAgIGJba10gPSBhW2krK107CiAgICAgICAgaSA9IGV5dHppbmdlcihpLCAyICogayArIDEpOwogICAgfQogICAgcmV0dXJuIGk7Cn0KCmludCBzZWFyY2goaW50IHgpIHsKICAgIGludCBrID0gMTsKICAgIHdoaWxlIChrIDw9IG4pIHsKICAgICAgICBfX2J1aWx0aW5fcHJlZmV0Y2goYiArIGsgKiBibG9ja19zaXplKTsKICAgICAgICBrID0gMiAqIGsgKyAoYltrXSA8IHgpOwogICAgfQogICAgcmV0dXJuIGsgLSBuICsgMTsKfQoKaW50IG1haW4oKSB7CglzdGQ6OmNvdXQgPDwgc3RkOjpmaXhlZCA8PCBzdGQ6OnNldHByZWNpc2lvbigzKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJYVtpXSA9IGk7Cgl9CglleXR6aW5nZXIoKTsKCXsKCQlkb3VibGUgdGluID0gKGRvdWJsZSljbG9jaygpOwoJCXVpbnQzMl90IHggPSAxLCBjaGVjayA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCAoMSA8PCAyMCk7IGkrKykgewoJCQl4ID0geG9yc2hpZnQzMih4KTsKCQkJY2hlY2sgXj0gc2VhcmNoKHggJSBuKTsKCQl9CgkJZG91YmxlIHRvdXQgPSAoZG91YmxlKWNsb2NrKCk7CgkJc3RkOjpjb3V0IDw8ICJleXR6aW5nZXIgPSAiIDw8ICh0b3V0IC0gdGluKSAvIENMT0NLU19QRVJfU0VDIDw8ICJzLCBjaGVjayA9ICIgPDwgY2hlY2sgPDwgc3RkOjplbmRsOwoJfQoJewoJCWRvdWJsZSB0aW4gPSAoZG91YmxlKWNsb2NrKCk7CgkJdWludDMyX3QgeCA9IDEsIGNoZWNrID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8ICgxIDw8IDIwKTsgaSsrKSB7CgkJCXggPSB4b3JzaGlmdDMyKHgpOwoJCQljaGVjayBePSBpbnQoc3RkOjpsb3dlcl9ib3VuZChhLCBhICsgbiwgeCAlIG4pIC0gYSk7CgkJfQoJCWRvdWJsZSB0b3V0ID0gKGRvdWJsZSljbG9jaygpOwoJCXN0ZDo6Y291dCA8PCAibG93ZXJfYm91bmQgPSAiIDw8ICh0b3V0IC0gdGluKSAvIENMT0NLU19QRVJfU0VDIDw8ICJzLCBjaGVjayA9ICIgPDwgY2hlY2sgPDwgc3RkOjplbmRsOwoJfQoJcmV0dXJuIDA7Cn0=