mblazev's blog

By mblazev, history, 6 years ago, In English

My hacked solution: https://codeforces.me/contest/1132/submission/50838954

On the worst possible test (test 52):

5000 5000
1 5000
...
1 5000

It just barely passes with >255 mb used. Memory usage is high beceause I fill all of those 5000 vectors with as much as data possible. However, a slightly different test (generated hack):

5000 5000
(randomly choose 1 or 2) 5000
...

Causes MLE. How could this be? Is it possible that generator affects memory usage? It MLE on that same hack upon resubmit though.

  • Vote: I like it
  • +17
  • Vote: I do not like it

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

git gud and solve it without 255MB of memory

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If only I had written short instead of int I would have been purple now :( So sad. I even considered that memory would be issue but it didnt occur to me to use short to be on the safe side.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Or maybe

      for (int j = l[i]; j <= r[i]; ++j)
          if( v[j].size() < 3 ) v[j].push_back(i);
      
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You mean < 3. That also needs to be distinguished because i can remove 2 painters. But yeah. Learning to be more careful the hard way :))

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

c1729 is more powerful than compiler optimizations :orz: