2770 - C++: tle. como optimizar? - URI Online Judge
C++: TLE. Como optimizar?
Daniel Koga asked 4 months ago
Primeiro eu tentei do modo óbvio, tomei as duas dimensões A e B da placa e as duas dimensões A e B do projeto e fiz as comparações:
Question solved. Code removed.
As duas duplas de teste são necessárias, pois o problema não explicita a orientação da placa e dos projetos. Num primeiro passo de optimização, é possível eliminar uma das duplas de teste se forçarmos a orientação. Dei uma pesquisada sobre e achei essa página com métodos para se calcular o mínimo e o máximo entre dois números sem usar testes:
https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/
Usando ele, o código fica:
Escrevi essa cadeia de variáveis ao invés de usar somente uma linha para evitar recálculos, afinal dXY é calculado 4 vezes e dXYSigned, duas.
Por fim, resolvi eliminar mais um teste fazendo algo simples. Ao invés de testar cada dimensão ordenada separadamente, testei as duas ao mesmo tempo, concatenando elas. Por exemplo, se as dimensões da placa são 4 e 12, as dimensões concatenadas (na base 10) seriam 1204. No meu código, fiz a concatenação em base binária e considerando que 64 = 2^6:
E ainda continuo tomando TLE. Fiz uns testes usando o header chrono e uma entrada gigante de umas 10000 linhas e os resultados foram todos semelhantes, antes e depois de tudo isso e mesmo não usando nenhuma flag de optimização.
Alguém pode dar uma dica sobre o que posso explorar para realmente optimizar esse código?
feodorv replied 4 months ago
Seems your TLE is due to the incorrect input reading.
Daniel Koga replied 4 months ago
On point, Feodorv. Thank you!
It seens the int I declared wasn't enough for 10^5 projects. Also, I redid the test (there were cases it couldn't handle correctly) and now I got it.