Pada mi na 8. i 9. test primjeru ( prekoraceno vremensko ogranicenje ). Probao sam i sa tournament stablom. Svejedno presporo. Koja je fora u ovom zadatku?
Saksije
Malo sam optimizirao update i query tournamenta i sada tijesno prolazi. Prvo slanje mi je dalo prekoraceno vremensko ogranicenje, ali drugi pokusaj je uspio.
9. test primjer ide u 0.97 sekundi. :)
9. test primjer ide u 0.97 sekundi. :)
Nemam pojma sta si ti ovde napricao, ali je dovoljno iz prvog u kom ima viska prebacivati u prvi u kom ima manjka i tako dok svi ne budu na svom.
Tocno, i to se moze napraviti u O( N ).
Ja sam radio ovako:
Za svaku teglu, ako ima viska, prebaci se u sljedecu. Ako ima manjka, treba uzeti iz prve u kojoj ima viska. Da nadjem takvu prvu trebao sam tournament stablo i ukupna slozenost mi je O( N lg N ), sto je ipak previse, ali je meni uz malo optimizacije i srece proslo :)
Ja sam radio ovako:
Za svaku teglu, ako ima viska, prebaci se u sljedecu. Ako ima manjka, treba uzeti iz prve u kojoj ima viska. Da nadjem takvu prvu trebao sam tournament stablo i ukupna slozenost mi je O( N lg N ), sto je ipak previse, ali je meni uz malo optimizacije i srece proslo :)
Ma to je najobicniji greedy, resenje je u 3 reda, pogledaj na yuoi