#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); }
}
};
template<int n, typename T>
int loserBound(const T* __restrict arr, const T val) {
return int(std::lower_bound(arr,arr+n,val)-arr);
}
uint32_t xorshift32(uint32_t x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
int main() {
static uint32_t arr[1 << 20];
uint32_t state = 111;
for (int i = 0; i < (1 << 20); i++) { state = arr[i] = xorshift32(state); }
std::sort(arr,arr+(1<<20));
#define TEST(s, f) \
{ \
std::cout << s << std::endl; \
int res = 0; \
double tin = (double)clock(), tout; \
uint32_t q = 123; \
for (int i = 0; i < (1 << 23); i++) \
res += f<1<<20>(&arr[0], q = xorshift32(q));\
tout = (double)clock(); \
std::cout << "time = " << (tout - tin) / CLOCKS_PER_SEC << "s, sum = " << res << std::endl; \
}
TEST("Testing std::lower_bound...", loserBound);
TEST("Testing lowerBound...", lowerBound);
return 0;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnRlbXBsYXRlPGludCBuLCB0eXBlbmFtZSBUPgppbnQgbG93ZXJCb3VuZChjb25zdCBUKiBfX3Jlc3RyaWN0IGFyciwgY29uc3QgVCB2YWwpIHsKCWlmIChuID09IDEpIHsgcmV0dXJuIHZhbCA+IGFyclswXTsgfSAKCWVsc2UgewoJCWNvbnN0ZXhwciBpbnQgbWlkID0gbiAvIDI7CgkJaWYgKHZhbCA+IGFyclttaWRdKSB7IHJldHVybiBtaWQrbG93ZXJCb3VuZDxuLW1pZCwgVD4oYXJyK21pZCwgdmFsKTsgfQoJCWVsc2UgeyByZXR1cm4gbG93ZXJCb3VuZDxtaWQsIFQ+KGFycix2YWwpOyB9Cgl9Cn07Cgp0ZW1wbGF0ZTxpbnQgbiwgdHlwZW5hbWUgVD4KaW50IGxvc2VyQm91bmQoY29uc3QgVCogX19yZXN0cmljdCBhcnIsIGNvbnN0IFQgdmFsKSB7CiAgICByZXR1cm4gaW50KHN0ZDo6bG93ZXJfYm91bmQoYXJyLGFycituLHZhbCktYXJyKTsKfQoKdWludDMyX3QgeG9yc2hpZnQzMih1aW50MzJfdCB4KSB7Cgl4IF49IHggPDwgMTM7Cgl4IF49IHggPj4gMTc7Cgl4IF49IHggPDwgNTsKCXJldHVybiB4Owp9CgppbnQgbWFpbigpIHsKCXN0YXRpYyB1aW50MzJfdCBhcnJbMSA8PCAyMF07Cgl1aW50MzJfdCBzdGF0ZSA9IDExMTsKCWZvciAoaW50IGkgPSAwOyBpIDwgKDEgPDwgMjApOyBpKyspIHsgc3RhdGUgPSBhcnJbaV0gPSB4b3JzaGlmdDMyKHN0YXRlKTsgfQoJc3RkOjpzb3J0KGFycixhcnIrKDE8PDIwKSk7CgkjZGVmaW5lIFRFU1QocywgZikgXAoJeyBcCgkJc3RkOjpjb3V0IDw8IHMgPDwgc3RkOjplbmRsOyBcCgkJaW50IHJlcyA9IDA7IFwKCQlkb3VibGUgdGluID0gKGRvdWJsZSljbG9jaygpLCB0b3V0OyBcCgkJdWludDMyX3QgcSA9IDEyMzsgXAoJCWZvciAoaW50IGkgPSAwOyBpIDwgKDEgPDwgMjMpOyBpKyspIFwKCQkJcmVzICs9IGY8MTw8MjA+KCZhcnJbMF0sIHEgPSB4b3JzaGlmdDMyKHEpKTtcCgkJdG91dCA9IChkb3VibGUpY2xvY2soKTsgXAoJCXN0ZDo6Y291dCA8PCAidGltZSA9ICIgPDwgKHRvdXQgLSB0aW4pIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgInMsIHN1bSA9ICIgPDwgcmVzIDw8IHN0ZDo6ZW5kbDsgXAoJfQoJVEVTVCgiVGVzdGluZyBzdGQ6Omxvd2VyX2JvdW5kLi4uIiwgbG9zZXJCb3VuZCk7CglURVNUKCJUZXN0aW5nIGxvd2VyQm91bmQuLi4iLCBsb3dlckJvdW5kKTsKCXJldHVybiAwOwp9