please add this test, i AC this problem in 0.812s, but my code answer to this code more than 1 second, in my computer, i think my computer is faster than the judge computer, sorry for my poor english.here is the test: 5000 4294967295 4294967295 4294967295 4294967295 (2500 times) 0 0 0 0 (2500 times)
...And not as difficult as it seems to be. My program on Pascal gets AC within 0.796 sec without complicated optimizations and even without sorting, grouping, ets. Just some good precalc ideas realized properly :)
Second code is UB (undefind behavour). C++ standard do not define variable "possitions" in heap. As far as first one, I think it is also UB, however I am not sure about this.
One time C++ optimizator just puts all 3 arrays "near". And second time, because of 3 different declatations, optimizator can make aligning to memory pages and put begining of each array into new page, this can make your program a little bit faster. But going out out bounds gets access violation now.
Question: Why do I have to write for j:=1 to 4 do begin read(b); a[i,j]:=b; end; instead of read(a[i,1],a[i,2],a[i,3],a[i,4]); ?
program ural1318; const maxn=5000; base=4294967296; maxe=38; type bignum=array[1..4]of int64; var e:array[0..maxe]of bignum; a:array[1..maxn]of bignum; n,i,j:word; ans,b:cardinal; function x(a,b:bignum):bignum; var i:byte; begin for i:=1 to 4 do x[i]:=a[i] xor b[i]; end; function smaller(a,b:bignum):boolean; var i:byte; begin for i:=1 to 4 do if a[i]<b[i] then begin smaller:=true;exit; end else if a[i]>b[i] then begin smaller:=false;exit; end; smaller:=false; end; function f(a:bignum):byte; var l,r,m:byte; begin l:=0;r:=maxe; repeat m:=(l+r+1) div 2; if smaller(a,e[m]) then r:=m-1 else l:=m; until l=r; f:=l; end; begin e[0,4]:=1; for i:=1 to maxe do for j:=4 downto 1 do begin inc(e[i,j],e[i-1,j]*10); if e[i,j]>=base then begin e[i,j-1]:=trunc(e[i,j]/base); dec(e[i,j],trunc(e[i,j-1]*base)); end; end; e[0,4]:=0;
read(n); for i:=1 to n do begin for j:=1 to 4 do begin read(b); a[i,j]:=b; end; for j:=1 to i-1 do inc(ans,f(x(a[i],a[j]))); end; writeln(ans*2); end.
In first: it is not correct to show this your solution (even wrong), please clear it, it already too bad.
In second: for I:=1 to N do readln(A[I],A[I],A[I],A[I]); - is correct pascal-line, where type TNum=array[0..3] of longword var A:array[1..5000] of TNum;
In third: to get AC your are to ULTRA-STRICT optimization. That meens some ASM-inline commands (bad way) or usual Pascal high-optimized code (depresive way).
For example: my AC program (0.703 461 КБ) use two usual cycles (two "repeat", o(n*n/2)), and a LOG calculation code (about 650 lines).
650 lines was generated by my special generation program. This code consists only "IF" operator, "XOR" and ":=" operator. Some path of this code here: -----BEGIN LOG-FUNCTION---------------------- v:=A^xor B^; if v<1 then begin v:=A^xor B^; if v<5 then begin v:=A^xor B^; if v<2 then begin v:=A^xor B^; if v<1 then log:=0 else if v=1 then begin log:=0; end else begin if v<100000 then --....--------------------- if v<232830 then begin if v<232 then begin if v<23 then log:=10 else if v>23 then log:=11 else begin v:=A^xor B^; if v>=1215752192 then log:=11 else log:=10; begin end; end end else if v>232 then begin if v<2328 then begin if v<2328 then log:=12 else if v>2328 then log:=13 --....--------------------- then log:=log*2; To generate this code I use several recurse functions and binary search of course. Think better and get AC 1318(1/1) as my.
I think O(n^2) algorithms will certainly lead to TLE. I tried to count how many results will be larger than 10,100,... and got an algorithm, and its complexity is O(800nlogn), still TLE. I heard that there was an O(n) algorithm, can anyone tell me how to do that? Thanks.
You should use a table, which for every 2^k (0 <= k <= 127) keeps a value of Trunc(log10(2^k)). You should also keep a table with powers of 10 (10^0 .. 10^39). In the main loop of the program (which is straight-forward) you compute B = A[i] XOR A[j], then find the position k of the most significant bit of B (k is counted from zero). k is obtained using assembler instruction BSR (Bit Scan Reverse). At this point you know that 2^k <= B < 2^(k+1). Now, M := Trunc(log10(2^k)), and N := Trunc(log10(2^(k+1)). If B >= 10^N, then Trunc(log10(B))=N, else Trunc(log10(B))=M.
Starting with this algorithm and optimizing it, you should get AC.