is operations of int64(pascal) slower than long long(c++)?

I really optimized my prog to got AC(I write at Pascal).

Please say how you did that on Pascal
my algo O(N^3*logX)
It work fast on my computer, but not on Timus :(

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.

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:43

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.

19 authors get AC instead of TLE. 7 of them increase their score by 1 problem!

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

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

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.