Why isn't there TLE?
I was solving the D problem of the previous contest Div2.907
I used binary search, but it needed ridiculous optimizations before it got accepted, and even then, it was a close call.
I played around for a while trying to make it even closer.
After all a while, I noticed....
That, codeforces forgot what TLE is.
This is a supreme example of machine learning that will be of great service to all competitive programmers worldwide.
A 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.
My Entire Program
#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";
}
The solve() function that should create TLE
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";
}
These are the links to my last attempts
- 230780232 This submission ran till test 17 before TLE occurred, some kind of self-realisation, maybe?!
- 230780567 My next attempt was totally unsuccessful, it got accepted, what a pity!!
