Why isn't there TLE?↵
==================↵
↵
I was solving the D problem of the previous contest Div2.907 <br>↵
I used binary search, but it needed ridiculous optimizations before it got accepted, and even then, it was a close call. <br>↵
I played around for a while trying to make it even closer. <br>↵
After all a while, I noticed.... <br>↵
↵
That, codeforces forgot what TLE is.↵
↵
As far as I can make out, this is a supreme example of machine learning that in the future, should be of great service to all competitive programmers worldwide.↵
↵
I made a last attempt at manufacturing a TLE, unfortunately, I failed to get it. It was very disappointing for me. As a competitive programmer, I thought that though I couldn't get AC all the time, at least I could get TLE, if I wanted. Apparently, even this is beyond my ability.↵
↵
↵
↵
<spoiler summary="My Entire Program">↵
```c++↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#ifdef LOCAL_MACHINE↵
template <class K, class V> ostream& operator<< (ostream& s, const pair <K, V> &p) {↵
auto [x, y] = p; s << '(' << x << ", " << y << ")"; return s;↵
}↵
template <class T, class=typename T::value_type, class=typename enable_if<!is_same<T, string>::value && !is_same<T, complex <typename T::value_type>>::value>::type> ostream& operator<< (ostream &out, const T&v) {↵
stringstream t; t << '{'; for(auto &x: v) {t << x << ", ";} ↵
string s = t.str(); if(!v.empty()) {s.pop_back(); s.pop_back();} s += '}'; ↵
out << s; return out;↵
}↵
template <class T> void __prnt(T x) {cerr << x << endl;}↵
void __prnt() {cerr << endl;}↵
template <class T, class...Ts> void __prnt (T&&a, Ts&&...etc) {cerr << a << ", ", __prnt(etc...);}↵
#define print(...) if(#__VA_ARGS__ == "") __prnt(); else (cerr << #__VA_ARGS__ <<" = ", __prnt(__VA_ARGS__))↵
#else↵
#define print(...) 4224224↵
#endif↵
↵
#define int long long↵
↵
const int MOD = 1000 * 1000 * 1000 + 7;↵
int mod(int n) {↵
return ((n % MOD) + MOD) % MOD;↵
}↵
↵
int epicmul(int a, int b) {↵
a = mod(a);↵
b = mod(b);↵
↵
if(b == 0)↵
return 0;↵
int x = epicmul(a, b / 2);↵
if(b % 2 == 0)↵
return mod(2ULL * x);↵
else↵
return mod(2ULL * x + a);↵
}↵
↵
typedef vector <int> vi;↵
typedef pair <int, int> pii;↵
↵
void solve();↵
void init();↵
↵
void maxeq(int &a, int b) {a = max(a, b);}↵
void mineq(int &a, int b) {a = min(a, b);}↵
↵
signed main() {↵
int t = 1;↵
cin >> t;↵
↵
while(t-- > 0) {↵
solve();↵
}↵
}↵
↵
↵
vector <vi> rngs = {{4, 7, 2}, {8, 8, 1}, {9, 15, 2}, {16, 31, 2}, {32, 63, 2}, {64, 127, 2}, {128, 255, 2}, {256, 511, 2}, {512, 728, 2}, {729, 1023, 3}, {1024, 2047, 3}, {2048, 4095, 3}, {4096, 8191, 3}, {8192, 16383, 3}, {16384, 32767, 3}, {32768, 50624, 3}, {50625, 65535, 4}, {65536, 131071, 4}, {131072, 262143, 4}, {262144, 524287, 4}, {524288, 1048575, 4}, {1048576, 2097151, 4}, {2097152, 4084100, 4}, {4084101, 4194303, 5}, {4194304, 5153631, 4}, {5153632, 8388607, 5}, {8388608, 16777215, 5}, {16777216, 33554431, 5}, {33554432, 67108863, 5}, {67108864, 134217727, 5}, {134217728, 268435455, 5}, {268435456, 481890303, 5}, {481890304, 536870911, 6}, {536870912, 594823320, 5}, {594823321, 1073741823, 6}, {1073741824, 2147483647, 6}, {2147483648, 4294967295, 6}, {4294967296, 8589934591, 6}, {8589934592, 17179869183, 6}, {17179869184, 34359738367, 6}, {34359738368, 64339296874, 6}, {64339296875, 68719476735, 7}, {68719476736, 78364164095, 6}, {78364164096, 137438953471, 7}, {137438953472, 274877906943, 7}, {274877906944, 549755813887, 7}, {549755813888, 1099511627775, 7}, {1099511627776, 2199023255551, 7}, {2199023255552, 4398046511103, 7}, {4398046511104, 8796093022207, 7}, {8796093022208, 11688200277600, 7}, {11688200277601, 17592186044415, 8}, {17592186044416, 35184372088831, 8}, {35184372088832, 70368744177663, 8}, {70368744177664, 140737488355327, 8}, {140737488355328, 281474976710655, 8}, {281474976710656, 562949953421311, 8}, {562949953421312, 1125899906842623, 8}, {1125899906842624, 1953124999999999, 8}, {1953125000000000, 2251799813685247, 9}, {2251799813685248, 2334165173090450, 8}, {2334165173090451, 4503599627370495, 9}, {4503599627370496, 9007199254740991, 9}, {9007199254740992, 18014398509481983, 9}, {18014398509481984, 36028797018963967, 9}, {36028797018963968, 72057594037927935, 9}, {72057594037927936, 144115188075855871, 9}, {144115188075855872, 288230376151711743, 9}, {288230376151711744, 430804206899405823, 9}, {430804206899405824, 576460752303423487, 10}, {576460752303423488, 1152921504606846975, 10}};↵
↵
vector <int> prefix = {8, 9, 23, 55, 119, 247, 503, 1015, 1449, 2334, 5406, 11550, 23838, 48414, 97566, 151137, 210781, 472925, 997213, 2045789, 4142941, 8337245, 16285041, 16836056, 20673368, 36848248, 78791288, 162677368, 330449528, 665993848, 337082481, 404356714, 734240362, 24002400, 897513404, 339964299, 224866096, 994669697, 534276885, 613491268, 490841050, 152099860, 20223614, 543746355, 616413925, 761749065, 52419338, 633759898, 796441011, 121803230, 872449273, 758253169, 245623331, 220363662, 169844324, 68805648, 866728303, 462573599, 161508000, 465858721, 336487884, 288333919, 650941611, 376156988, 826587749, 727449264, 529172294, 132618354, 879713805, 723932337, 405914836};↵
↵
↵
int find_range(int x) {↵
int l = -1;↵
int r = rngs.size();↵
↵
while(r - l > 1) {↵
int m = (l + r) / 2;↵
vi rng = rngs[m];↵
↵
if(rng[0] <= x)↵
l = m;↵
else↵
r = m;↵
}↵
return l;↵
}↵
↵
int get(int l, int r, int v) {↵
int size = mod(mod(r) - mod(l) + 1);↵
return epicmul(size, v);↵
}↵
↵
void solve() {↵
int l, r;↵
cin >> l >> r;↵
↵
int a = find_range(l);↵
int b = find_range(r);↵
↵
int ans = 0;↵
↵
int res = 0;↵
int lim = 10000000LL;↵
//1↵
for(int i = 0; i < lim; i++) {↵
for(int j = 0; j < lim; j++) {↵
for(int k = 0; k < lim; k++) {↵
for(int l = 0; l < lim; l++) {↵
ans++;↵
res++; ↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
↵
if(a + 1 <= b - 1) {↵
ans = mod(ans + prefix[b - 1] - prefix[a]);↵
}↵
↵
if(a != b) {↵
ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));↵
ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));↵
} else ↵
ans = mod(ans + get(l, r, rngs[a][2]));↵
↵
//cout << ans << "\n";↵
cout << ans << "\n";↵
}↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
<spoiler summary="The solve() function that should create TLE">↵
```c++↵
void solve() {↵
int l, r;↵
cin >> l >> r;↵
↵
int a = find_range(l);↵
int b = find_range(r);↵
↵
int ans = 0;↵
↵
int res = 0;↵
int lim = 10000000LL;↵
//1↵
for(int i = 0; i < lim; i++) {↵
for(int j = 0; j < lim; j++) {↵
for(int k = 0; k < lim; k++) {↵
for(int l = 0; l < lim; l++) {↵
ans++;↵
res++; ↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
↵
if(a + 1 <= b - 1) {↵
ans = mod(ans + prefix[b - 1] - prefix[a]);↵
}↵
↵
if(a != b) {↵
ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));↵
ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));↵
} else ↵
ans = mod(ans + get(l, r, rngs[a][2]));↵
↵
//cout << ans << "\n";↵
cout << ans << "\n";↵
}↵
↵
```↵
</spoiler>↵
↵
↵
↵
These are the links to my last attempts <br>↵
- [submission:230780232] This submission ran till test 17 before TLE occurred, some kind of self-realisation, maybe?! <br>↵
- [submission:230780567] My next attempt was totally unsuccessful, it got AC, what a pity.↵
↵
On my local system, things work as normal. I'm currently expecting to see some output after a few decades.↵
↵
As these violations of the universe are beyond my sphere of comprehension, could any wise sage possibly enlighten me?↵
==================↵
↵
I was solving the D problem of the previous contest Div2.907 <br>↵
I used binary search, but it needed ridiculous optimizations before it got accepted, and even then, it was a close call. <br>↵
I played around for a while trying to make it even closer. <br>↵
After all a while, I noticed.... <br>↵
↵
That, codeforces forgot what TLE is.↵
↵
As far as I can make out, this is a supreme example of machine learning that in the future, should be of great service to all competitive programmers worldwide.↵
↵
I made a last attempt at manufacturing a TLE, unfortunately, I failed to get it. It was very disappointing for me. As a competitive programmer, I thought that though I couldn't get AC all the time, at least I could get TLE, if I wanted. Apparently, even this is beyond my ability.↵
↵
↵
↵
<spoiler summary="My Entire Program">↵
```c++↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#ifdef LOCAL_MACHINE↵
template <class K, class V> ostream& operator<< (ostream& s, const pair <K, V> &p) {↵
auto [x, y] = p; s << '(' << x << ", " << y << ")"; return s;↵
}↵
template <class T, class=typename T::value_type, class=typename enable_if<!is_same<T, string>::value && !is_same<T, complex <typename T::value_type>>::value>::type> ostream& operator<< (ostream &out, const T&v) {↵
stringstream t; t << '{'; for(auto &x: v) {t << x << ", ";} ↵
string s = t.str(); if(!v.empty()) {s.pop_back(); s.pop_back();} s += '}'; ↵
out << s; return out;↵
}↵
template <class T> void __prnt(T x) {cerr << x << endl;}↵
void __prnt() {cerr << endl;}↵
template <class T, class...Ts> void __prnt (T&&a, Ts&&...etc) {cerr << a << ", ", __prnt(etc...);}↵
#define print(...) if(#__VA_ARGS__ == "") __prnt(); else (cerr << #__VA_ARGS__ <<" = ", __prnt(__VA_ARGS__))↵
#else↵
#define print(...) 4224224↵
#endif↵
↵
#define int long long↵
↵
const int MOD = 1000 * 1000 * 1000 + 7;↵
int mod(int n) {↵
return ((n % MOD) + MOD) % MOD;↵
}↵
↵
int epicmul(int a, int b) {↵
a = mod(a);↵
b = mod(b);↵
↵
if(b == 0)↵
return 0;↵
int x = epicmul(a, b / 2);↵
if(b % 2 == 0)↵
return mod(2ULL * x);↵
else↵
return mod(2ULL * x + a);↵
}↵
↵
typedef vector <int> vi;↵
typedef pair <int, int> pii;↵
↵
void solve();↵
void init();↵
↵
void maxeq(int &a, int b) {a = max(a, b);}↵
void mineq(int &a, int b) {a = min(a, b);}↵
↵
signed main() {↵
int t = 1;↵
cin >> t;↵
↵
while(t-- > 0) {↵
solve();↵
}↵
}↵
↵
↵
vector <vi> rngs = {{4, 7, 2}, {8, 8, 1}, {9, 15, 2}, {16, 31, 2}, {32, 63, 2}, {64, 127, 2}, {128, 255, 2}, {256, 511, 2}, {512, 728, 2}, {729, 1023, 3}, {1024, 2047, 3}, {2048, 4095, 3}, {4096, 8191, 3}, {8192, 16383, 3}, {16384, 32767, 3}, {32768, 50624, 3}, {50625, 65535, 4}, {65536, 131071, 4}, {131072, 262143, 4}, {262144, 524287, 4}, {524288, 1048575, 4}, {1048576, 2097151, 4}, {2097152, 4084100, 4}, {4084101, 4194303, 5}, {4194304, 5153631, 4}, {5153632, 8388607, 5}, {8388608, 16777215, 5}, {16777216, 33554431, 5}, {33554432, 67108863, 5}, {67108864, 134217727, 5}, {134217728, 268435455, 5}, {268435456, 481890303, 5}, {481890304, 536870911, 6}, {536870912, 594823320, 5}, {594823321, 1073741823, 6}, {1073741824, 2147483647, 6}, {2147483648, 4294967295, 6}, {4294967296, 8589934591, 6}, {8589934592, 17179869183, 6}, {17179869184, 34359738367, 6}, {34359738368, 64339296874, 6}, {64339296875, 68719476735, 7}, {68719476736, 78364164095, 6}, {78364164096, 137438953471, 7}, {137438953472, 274877906943, 7}, {274877906944, 549755813887, 7}, {549755813888, 1099511627775, 7}, {1099511627776, 2199023255551, 7}, {2199023255552, 4398046511103, 7}, {4398046511104, 8796093022207, 7}, {8796093022208, 11688200277600, 7}, {11688200277601, 17592186044415, 8}, {17592186044416, 35184372088831, 8}, {35184372088832, 70368744177663, 8}, {70368744177664, 140737488355327, 8}, {140737488355328, 281474976710655, 8}, {281474976710656, 562949953421311, 8}, {562949953421312, 1125899906842623, 8}, {1125899906842624, 1953124999999999, 8}, {1953125000000000, 2251799813685247, 9}, {2251799813685248, 2334165173090450, 8}, {2334165173090451, 4503599627370495, 9}, {4503599627370496, 9007199254740991, 9}, {9007199254740992, 18014398509481983, 9}, {18014398509481984, 36028797018963967, 9}, {36028797018963968, 72057594037927935, 9}, {72057594037927936, 144115188075855871, 9}, {144115188075855872, 288230376151711743, 9}, {288230376151711744, 430804206899405823, 9}, {430804206899405824, 576460752303423487, 10}, {576460752303423488, 1152921504606846975, 10}};↵
↵
vector <int> prefix = {8, 9, 23, 55, 119, 247, 503, 1015, 1449, 2334, 5406, 11550, 23838, 48414, 97566, 151137, 210781, 472925, 997213, 2045789, 4142941, 8337245, 16285041, 16836056, 20673368, 36848248, 78791288, 162677368, 330449528, 665993848, 337082481, 404356714, 734240362, 24002400, 897513404, 339964299, 224866096, 994669697, 534276885, 613491268, 490841050, 152099860, 20223614, 543746355, 616413925, 761749065, 52419338, 633759898, 796441011, 121803230, 872449273, 758253169, 245623331, 220363662, 169844324, 68805648, 866728303, 462573599, 161508000, 465858721, 336487884, 288333919, 650941611, 376156988, 826587749, 727449264, 529172294, 132618354, 879713805, 723932337, 405914836};↵
↵
↵
int find_range(int x) {↵
int l = -1;↵
int r = rngs.size();↵
↵
while(r - l > 1) {↵
int m = (l + r) / 2;↵
vi rng = rngs[m];↵
↵
if(rng[0] <= x)↵
l = m;↵
else↵
r = m;↵
}↵
return l;↵
}↵
↵
int get(int l, int r, int v) {↵
int size = mod(mod(r) - mod(l) + 1);↵
return epicmul(size, v);↵
}↵
↵
void solve() {↵
int l, r;↵
cin >> l >> r;↵
↵
int a = find_range(l);↵
int b = find_range(r);↵
↵
int ans = 0;↵
↵
int res = 0;↵
int lim = 10000000LL;↵
//1↵
for(int i = 0; i < lim; i++) {↵
for(int j = 0; j < lim; j++) {↵
for(int k = 0; k < lim; k++) {↵
for(int l = 0; l < lim; l++) {↵
ans++;↵
res++; ↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
↵
if(a + 1 <= b - 1) {↵
ans = mod(ans + prefix[b - 1] - prefix[a]);↵
}↵
↵
if(a != b) {↵
ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));↵
ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));↵
} else ↵
ans = mod(ans + get(l, r, rngs[a][2]));↵
↵
//cout << ans << "\n";↵
cout << ans << "\n";↵
}↵
↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
<spoiler summary="The solve() function that should create TLE">↵
```c++↵
void solve() {↵
int l, r;↵
cin >> l >> r;↵
↵
int a = find_range(l);↵
int b = find_range(r);↵
↵
int ans = 0;↵
↵
int res = 0;↵
int lim = 10000000LL;↵
//1↵
for(int i = 0; i < lim; i++) {↵
for(int j = 0; j < lim; j++) {↵
for(int k = 0; k < lim; k++) {↵
for(int l = 0; l < lim; l++) {↵
ans++;↵
res++; ↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
ans++;↵
}↵
ans -= lim;↵
↵
if(a + 1 <= b - 1) {↵
ans = mod(ans + prefix[b - 1] - prefix[a]);↵
}↵
↵
if(a != b) {↵
ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));↵
ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));↵
} else ↵
ans = mod(ans + get(l, r, rngs[a][2]));↵
↵
//cout << ans << "\n";↵
cout << ans << "\n";↵
}↵
↵
```↵
</spoiler>↵
↵
↵
↵
These are the links to my last attempts <br>↵
- [submission:230780232] This submission ran till test 17 before TLE occurred, some kind of self-realisation, maybe?! <br>↵
- [submission:230780567] My next attempt was totally unsuccessful, it got AC, what a pity.↵
↵
On my local system, things work as normal. I'm currently expecting to see some output after a few decades.↵
↵
As these violations of the universe are beyond my sphere of comprehension, could any wise sage possibly enlighten me?↵
