macaquedev's blog

I think some people are hacking the CF algorithm
By macaquedev, history, 5 hours ago, In English

See this... How the hell does creating a 1e5 ish sized array 1e4 times pass?? I think he's probably hacked Codeforces or something...

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

»
5 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I think its fine. That is within the allowed number of iterations if you consider total tests.

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

    1e9 should not pass in 2 seconds

    → Reply
    • »
      »
      »
      4 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maximum number of iterations is ~63245 because $$$(N+1)*N/2<MAX$$$ .

      So in total it will be $$$6*(1e8)$$$ which is fine.

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

      Even if was a pure 1e9, it still depends on other constants. There are huge differences between performing 1e9 additions and 1e9 prints, and the former even fits in like 0.5s, whilte the latter can't run even in 10s. Pushing to a vector is a little more heavier, but 6e8 still barely fits in 2s.

      → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

it's not 1e9 iterations as it's increasing each time like this 1 3 6 10 15 21 27 so it's not 1e9 so it passed

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For every test case a new array of at max 1e4 will be created. Which is anyways fine. What is the problem here?

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because there are 1e4 testcases, and push_back is slow...

    → Reply
»
3 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

Eliminated.

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you do it? Can you tell me what testcase you used? I did the maximal one (1 1000000000, repeated 10000 times) and that did not TLE...

    → Reply