rick_sanchez_c-137's blog

By rick_sanchez_c-137, history, 7 years ago, In English

Hello!

Regarding this line sweep problem with the editorial here my code is getting run time error on the last test case. I contacted the team support from the online judge Kattis but they did not allow me to see the test case where my code fails.

Can someone spot any mistake in my code I possibly made?

Thanks a lot in advance!

EDIT: In another submission (code here) when adding "if(it==mx1.end()) continue;" in line 180 I get WA instead of RE. Plus if I loop over all elements of the multiset when set.find fails (fail = returns set.end()) I get TLE as in this code. By looping over all elements the code seem to find the segment I want, but by a "manual" manner that is not fast enough. I only get the mentioned errors in the last test case that was created by the Kattis (not created by original author — a link I left on the comments may be useful to understand the situation). Also just so you know, kattis does not allow me to share the code straight from my account there, so I need to do it by pastebin.

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

Use google to find testcases

https://ncpc.idi.ntnu.no/ncpc2013/

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

    Actually my code works for the test cases from the original contest. The thing is that Kattis changed the test cases because they thought it was too weak and allowed buggy code to be accepted. Here is my conversation with the support team

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

Possible problem: you're using multiset with comparator cmp1 which compares by long double x() without applying EPS.

On the other hand you use x() only for comparison in multiset, and it looks like a.x() < b.x() can be rewritten using only integer comparison.

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

    Tryed it and still got RE, as in here

    Long double should work because the smallest diference between two quotients of magnitude 10^n is 1/(10^(2n)) (where n is 6 in the problem, and long double has 18 significant figures)