is operations of int64(pascal) slower than long long(c++)?
Послано
frost 16 дек 2006 14:32
is operations of int64(pascal) slower than long long(c++)?
I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
I really optimized my prog to got AC(I write at Pascal).
Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
Please say how you did that on Pascal
my algo O(N^3*logX)
It work fast on my computer, but not on Timus :(
Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
Послано
Nick J 19 дек 2006 18:39
Me and my friend had exactly the same algorithm and optomization but my program needs 1.7 and his needs 0.3secs (we both use C++)
It is very hard to solve it in Pascal, so use C++ :) or rewrite program several times.
The complaint is accepted (+)
It appeared, that FreePascal 2.0.4 compiler, which is used on Timus Online Judge, is extremely slow at arithmetical operations, especially on Int64-operands. "Mod" and "*" operations on Int64 are very slow. We did not expect such a thing, and we are sorry.
Anyway, the jury HAS correct Pascal solution, which passes the timelimit (2 seconds), so it is a question of justice only, not of jury mistakes, problem incorrectness and so on.
Now the timelimit is 3 seconds, and it is more than enough to solve this problem on Pascal without special optimization trick. My straightforward solution works exactly 2 second:
http://acm.timus.ru/status.aspx?space=1&num=1518&pos=1383115 The problem will be rejudged soon.
The performance of FreePascal 2.0.4 compiler in comparison with Delphi 7 compiler (dcc32 15.0) is under inverstigation. If Delphi appears to be faster (and it seems to be true), it would be added on Timus Online Judge. If you know the fastest Pascal compiler, please, tell us. It will be fair for Pascal programmers, because the fastest Intel C++ Compiler is used for C++.
Edited by author 19.12.2006 21:43Re: The complaint is accepted (+)
FreePascal generates very bad code for int64 multiplicatons.
I use Delphi 7.0 and on my computer (AthlonXP 2200)
my prog works 0.9 sec in worst case, but on Timus the
same prog works 2.093 sec.
I got AC in 1.261 sec with rewritng
multiplication on Assembler.
Problem has been rejudged (+)
19 authors get AC instead of TLE. 7 of them increase their score by 1 problem!
Re: Problem has been rejudged (+)
Послано
m2m 20 дек 2006 01:10
My algo is also N^3*log(X), but not accepted in C++.
how to solve it?
Time limit in test case 13. anyone helps me ?
Edited by author 20.12.2006 01:17
Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
Послано
asd 8 янв 2007 14:20
My solution is also O(logX*N^3) but my program written on Java works so slowly...
for example, It works about 6 seconds on test
100 268435455 268435455
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
I can't even imagine how to solve it without rewriting solution using another language...
Edited by author 08.01.2007 19:20
Ilya Grabnov's straightforward Java solution works 1.6 sec. (-)
Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-)
Since the matrix consists of only zeroes and ones, you can perform half of multiplications using just +, - and >= via 32bit types. Perform only squaring via __int64 and %. This helped to make my 2.9 sec C++ solution running at 1.5 sec.
