EXPOSED: The Leetcode C++ Cheat Code!!

Here's a fun story about stdin, stdout, and how Leetcode users use C++'s dark power to game the system a bit.

Strange Things are Afoot at the Circle K

A few days ago, I was minding my own business going through the binary search study plan on Leetcode.

I worked on my C++ submission, optimized it at the Compiler Explorer, and submitted it only to find that while my solution beat over 90% of others in terms of execution time, it only beat 15% of people in terms of memory usage.

When checking the solutions that beat mine, I first saw this:

Your placement in the rankings isn't normally a huge deal - especially in simpler challenges - due to fluctuations in Leetcode's runtime. Sometimes it uses 26.5MB or memory, and sometimes it takes 26.6. Your placement in the rankings is somewhat randomized due to this.

But the difference in this graph is astounding. 26.7MB down to 5.9! That's somehow a 77.1% reduction in RAM usage on a simple binary search.

What is going on?

The Cheat Code

Clicking into each of those < 10MB solutions above all revealed the same thing. The following code was written (likely pasted in), above the actual submissions!

int init=[] {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ofstream out("user.out");
  cout.rdbuf(out.rdbuf());

  for(string s; getline(cin,s); cout << '\n'){
    string t;
    getline(cin,t);
    int tar = stoi(t);

    for(int i = 0, _i = 1, _n = s.length(); _i<_n; ++I, ++_i){
      bool _neg = false;
      if(s[_i]=='-')++_i, _neg = true;
      int v = s[_i++]&15;
      while((s[_i]&15)<10)v = v*10 + (s[_i++]&15);

      if(_neg)v= -v;
      if(v == tar){
        cout << i;
        goto next;
      }

      if(v > tar)break;
    }

    cout << -1;
    next:;
  }

  exit(0);
  return 0;
}();

Explanation

So what the heck is going on with this code? I had to figure it out myself, so let me try and explain it to you.

IIFE Syntax

The first thing to note is that this code is an Immediately Invoked Function Expression or an IIFE. This means this function is executed (or invoked) immediately after it's defined.

In C++, the syntax is something like []{/* function stuff */}(); You might recognize its counterpart from JavaScript: (() => {})()

Why assign it to init? Long story short: so it will compile.

ios_base::sync_with_stdio(false);

By default, the input and output streams in C++ are synchronized with those of its predecessor, C. The theory is not so important for this explanation, because in practice what this means is you're doing duplicate work. This line of code turns this synchronization off.

Note that in this case the ios is "inputs and outputs" and not "iOS".

cin.tie(nullptr);

Similarly, C++'s own cin and cout streams are "tied" together in that flushing one will also flush the other. This disables that again preventing extra work.

Redirecting to user.out

The next two lines:

ofstream out("user.out");
cout.rdbuf(out.rdbuf());

Next, we redirect cout to a file called user.out, removing the time requirement of actually displaying anything on the console.

The nested for and while loops

This is the part that took me the longest to figure out - not only in terms of what the code does, but why?

What: In simple terms this part of the code reads in two lines of text, converts the second to an integer, and then returns the index of the first string that matches that integer.

Why: Since all the I/O synchronization and features are turned off above, the code within these loops is responsible for the actual processing of text.

I will admit that figuring out the bit shifting and integer casting of stdin and stdout is outside of my time box for writing this post, but if YOU know - explain it in the comments!