dimitris_rondo's blog

BOI 2017 strings
By dimitris_rondo, history, 7 years ago, In English

Hello,

I tried to solve BOI 2017 strings, but I got 40/100. I do not pass subtasks 1, 2, 5, so there must be some bug in the second modification query, which is to reverse a substring of the string. I tried to debug it, but I could not find the error. Any help would be appriciated. Here is my code.

Thanks

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

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When you push the reverse lazy, you should also swap the two children (t->l, t->r).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

On lines 36 and 40, where you swap the hashes of the children, you must not check if the children are to be reversed, so remove the if(t->l->rev), if(t->r->rev).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thank you very much!!!! 100/100 now.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      Also another way is to have two functions — one for pushing lazy and another for pushing up the values of the children. This way it's less confusing. I modified your code for that here. "operation" is the push up function and the "upd" is the push down.

      PS: it also passes for 100.

      → Reply