|
|
back to boardHow to prevent TLE? I use LinkedList (can AddFirst and AddLast) and use max size of set = n. I'll give you the same hint that helped me see the way: Note that there are a maximum of 10^6 operations. I use this fact: when copy operation occurs then I copy not whole set but only part of set (so size of set always <= n). But this doesn't prevent from TLE. So, how to copy rapidly (I copy element by element)? Hmm that sounds like the right idea, you might double check that your code matches your idea correctly. > 1.031 32 120 KB Looking at your submit data, you may need to be more aggressive in implementing your idea. Edited by author 24.10.2012 17:26 Now I use array with length 2*n instead of LinkedList. So, I decrease memory: >1.015 5 912 КБ But how to decrease time? =) Copy operation takes most time, but each time size of my array (amount of useful elemenets that can be pop) is not more than (n - i) elements. So, how to optimize copy operation? It's really hard to say without seeing code. If you're correctly managing copies like you say, you shouldn't TLE. Seems like you have a simple bug somewhere. Try creating more perosnal test cases that focus on copies to start with. I've overwritten my code from C# to C++ and use memcpy for quick copying but TLE42 again =). So, could you please send me your solution or tell me your mail to check my solution? My mail is on my profile page (hyperlink) From the site FAQ on C/C++: An example of how to use input/output is given above. C++ programmers may always choose between two input/output libraries: standard (scanf, printf) or stream (cin, cout) input/output. Stream input/output is easy to use, but it works much slower than standard input/output. This may even cause receiving the Time limit exceeded verdict. Therefore, if you see that a problem requires reading a lot of input data (for example, more than a megabyte) or a large output is expected, then you should better use standard input/output. Thank you, using of scanf and printf leads to AC. This is bad problem when your algorithm is not so neccessary as quick reading and writing. For C# coders: use Console.In.ReadToEnd - for reading whole input file, and use only once Console.Write for writing answer, and you'll get AC. I just can't understand, when I submit my code using g++4.7.2 c++11, I got TLE42, but vc++2010 or g++4.7.2, I can AC 0.64s. Then I try other problems I find g++4.7.2 is the best. Edited by author 26.04.2013 15:20 In Java use PrintWriter instead System.out.println. I have TLE 1.015 with System.out.println, and I have time 0.703 with PrintWriter. |
|
|