neat's blog

By neat, history, 5 years ago, In English

76778492

#include <bits/stdc++.h> 
using namespace std;
int main() { 
  long long t, n, p;
  cin >> t; 
  while(t--) 
  { 
    p = 0;
    cin >> n; 
    for(int i=0; i<n; i++) 
      for(int j=0; j<n; j++) 
        for(int k = 0; k < n; k++) 
          for(int l = 0; l < n; l++) 
            for(int m = 0; m < n; m++)
              for(int o = 0; o < n; o++)
                p++;
    p -= p;
    cout << p + n << "\n";
  }
  return 0; 
  
}

Above is one of my Accepted submissions for problem 1339A — Filling Diamonds from Codeforces Round #633 (Div. 2). The answer for the problem is same as the input $$$n$$$ for each testcase. Its complexity is $$$O(n^6)$$$ per testcase. Here $$$1 <= n <= 10^9$$$. I am wondering how it passed all testcases. Kindly write your thoughts in the comments section.

  • Vote: I like it
  • -13
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! An unfortunate way to answer that question.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yes. I made such a submission after seeing an $$$O(n)$$$ per testcase solution getting Accepted. Was shocked to see my $$$O(n^6)$$$ per testcase solution also getting Accepted.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Surprising!

»
5 years ago, # |
  Vote: I like it +55 Vote: I do not like it

its -O2 optimisation of the compiler.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Could you please elaborate on the optimisation? Thanks.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Its smart enough to notice that p is doing absolutely nothing.