#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
template<int n, typename T>
int lowerBound(const T* __restrict arr, const T val) {
if (n == 1) { return val > arr[0]; }
else {
constexpr int mid = n / 2;
if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
else { return lowerBound<mid, T>(arr,val); }
}
};
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;
}
{
double tin = (double)clock();
uint32_t x = 1, check = 0;
for (int i = 0; i < (1 << 20); i++) {
x = xorshift32(x);
check ^= lowerBound<n>(a, int(x % n));
}
double tout = (double)clock();
std::cout << "template = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
}
return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp0ZW1wbGF0ZTxpbnQgbiwgdHlwZW5hbWUgVD4KaW50IGxvd2VyQm91bmQoY29uc3QgVCogX19yZXN0cmljdCBhcnIsIGNvbnN0IFQgdmFsKSB7CiAgICBpZiAobiA9PSAxKSB7IHJldHVybiB2YWwgPiBhcnJbMF07IH0gCiAgICBlbHNlIHsKICAgICAgICBjb25zdGV4cHIgaW50IG1pZCA9IG4gLyAyOwogICAgICAgIGlmICh2YWwgPiBhcnJbbWlkXSkgeyByZXR1cm4gbWlkK2xvd2VyQm91bmQ8bi1taWQsIFQ+KGFycittaWQsIHZhbCk7IH0KICAgICAgICBlbHNlIHsgcmV0dXJuIGxvd2VyQm91bmQ8bWlkLCBUPihhcnIsdmFsKTsgfQogICAgfQp9OwoKdWludDMyX3QgeG9yc2hpZnQzMih1aW50MzJfdCB4KSB7Cgl4IF49IHggPDwgMTM7Cgl4IF49IHggPj4gMTc7CglyZXR1cm4geCBePSB4IDw8IDU7Cn0KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgbiA9ICgxPDwyMCk7CmNvbnN0IGludCBibG9ja19zaXplID0gMTY7CmFsaWduYXMoNjQpIGludCBhW25dLCBiW24gKiAyXTsKCmludCBleXR6aW5nZXIoaW50IGkgPSAwLCBpbnQgayA9IDEpIHsKICAgIGlmIChrIDw9IG4pIHsKICAgICAgICBpID0gZXl0emluZ2VyKGksIDIgKiBrKTsKICAgICAgICBiW2tdID0gYVtpKytdOwogICAgICAgIGkgPSBleXR6aW5nZXIoaSwgMiAqIGsgKyAxKTsKICAgIH0KICAgIHJldHVybiBpOwp9CgppbnQgc2VhcmNoKGludCB4KSB7CiAgICBpbnQgayA9IDE7CiAgICB3aGlsZSAoayA8PSBuKSB7CiAgICAgICAgX19idWlsdGluX3ByZWZldGNoKGIgKyBrICogYmxvY2tfc2l6ZSk7CiAgICAgICAgayA9IDIgKiBrICsgKGJba10gPCB4KTsKICAgIH0KICAgIHJldHVybiBrIC0gbiArIDE7Cn0KCmludCBtYWluKCkgewoJc3RkOjpjb3V0IDw8IHN0ZDo6Zml4ZWQgPDwgc3RkOjpzZXRwcmVjaXNpb24oMyk7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCWFbaV0gPSBpOwoJfQoJZXl0emluZ2VyKCk7Cgl7CgkJZG91YmxlIHRpbiA9IChkb3VibGUpY2xvY2soKTsKCQl1aW50MzJfdCB4ID0gMSwgY2hlY2sgPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgKDEgPDwgMjApOyBpKyspIHsKCQkJeCA9IHhvcnNoaWZ0MzIoeCk7CgkJCWNoZWNrIF49IHNlYXJjaCh4ICUgbik7CgkJfQoJCWRvdWJsZSB0b3V0ID0gKGRvdWJsZSljbG9jaygpOwoJCXN0ZDo6Y291dCA8PCAiZXl0emluZ2VyID0gIiA8PCAodG91dCAtIHRpbikgLyBDTE9DS1NfUEVSX1NFQyA8PCAicywgY2hlY2sgPSAiIDw8IGNoZWNrIDw8IHN0ZDo6ZW5kbDsKCX0KCXsKCQlkb3VibGUgdGluID0gKGRvdWJsZSljbG9jaygpOwoJCXVpbnQzMl90IHggPSAxLCBjaGVjayA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCAoMSA8PCAyMCk7IGkrKykgewoJCQl4ID0geG9yc2hpZnQzMih4KTsKCQkJY2hlY2sgXj0gaW50KHN0ZDo6bG93ZXJfYm91bmQoYSwgYSArIG4sIHggJSBuKSAtIGEpOwoJCX0KCQlkb3VibGUgdG91dCA9IChkb3VibGUpY2xvY2soKTsKCQlzdGQ6OmNvdXQgPDwgImxvd2VyX2JvdW5kID0gIiA8PCAodG91dCAtIHRpbikgLyBDTE9DS1NfUEVSX1NFQyA8PCAicywgY2hlY2sgPSAiIDw8IGNoZWNrIDw8IHN0ZDo6ZW5kbDsKCX0KCXsKCQlkb3VibGUgdGluID0gKGRvdWJsZSljbG9jaygpOwoJCXVpbnQzMl90IHggPSAxLCBjaGVjayA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCAoMSA8PCAyMCk7IGkrKykgewoJCQl4ID0geG9yc2hpZnQzMih4KTsKCQkJY2hlY2sgXj0gbG93ZXJCb3VuZDxuPihhLCBpbnQoeCAlIG4pKTsKCQl9CgkJZG91YmxlIHRvdXQgPSAoZG91YmxlKWNsb2NrKCk7CgkJc3RkOjpjb3V0IDw8ICJ0ZW1wbGF0ZSA9ICIgPDwgKHRvdXQgLSB0aW4pIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgInMsIGNoZWNrID0gIiA8PCBjaGVjayA8PCBzdGQ6OmVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==