Run this O(n^2) program in CF custom test
#include "bits/stdc++.h"
using namespace std;
long long n;
int main() {
cin >> n;
for(long long i = 1; i <= n; i++) {
for(long long j = 1; j <= n; j++) {
if((i ^ j) == 0) {
if(i != j) {
cout << "NO!\n";
return 0;
}
}
}
}
cout << "YES\n";
}
with n = 100000000000
You would expect it to be much longer than 1 second, but it takes
15 ms
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
(1^2)==0lol it's 3
lolz
Codeforces uses a thing named Compiler optimization.
But does it optimize it by that much?
actually it's not that much.
If $$$i \oplus j = 0$$$ then $$$i=j$$$.
However there's also a condition $$$i \neq j$$$, these conditions cannot be both
true.Socout<<"NO!";never processes.The compiler found it, and then skipped the whole procedure.
Thanks for the explanation!
The compiler probably ignores both loops, because these two conditions,
if(i ^ j == 0)andif(i != j)will never be true at the same time so it ignores everything as the loops aren't doing anything. Compiler automatically ignores redundant code like that.Thanks
https://godbolt.org/ — use this website to investigate such stuff. As you can see there is no assembler corresponding to loops. However, if you replace
if(i != j)withif(i != j + 1), you can see that asm suddenly becomes much more complicated. Conclusion: compiler indeed optimizes the loops away. I recommend you to play around with this stuff as you seem pretty interested in it. Another example of optimization:From length of assembler codes you can guess that only MVC and Clang, contrary to GCC don't optimize this loop to a formula. And even GCC wouldn't optimize
(a += 69ll*n + 420) %= 228. You can confirm those results using Costum Invocation. Go ahead and play around with this stuff!(a += 69ll*n + 420) %= 228