ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1028. Stars

Why WA on TEST1!?
Posted by Ulyanov Maxim (KazanSU) 29 Oct 2005 22:31
{$q+,r+,s+,t+}
const
  m=32768;
type
  key=record
      left,key,right:word;
      end;
var
  ans:array[0..14999]of word;
  d:array[1..2*m-1]of key;
  n,i,a,b:word;

procedure init;
var
  i:word;
begin
fillchar(d,sizeof(d),0);
d[1].left:=1;d[1].right:=m;
for i:=2 to 2*m-1 do
  if not(odd(i)) then
    begin
    d[i].left:=d[i shr 1].left;
    d[i].right:=(d[i shr 1].right-d[i shr 1].left)shr 1 +d[i].left;
    end
  else
    begin
    d[i].right:=d[i shr 1].right;
    d[i].left:=d[i].right-(d[i shr 1].right-d[i shr 1].left)shr 1;
    end;
end;

procedure modify(var i:word);
begin
repeat
inc(d[i].key);
i:=i shr 1;
until i=0;
end;

function count(var r:word):word;
var
  sum:word;
begin
i:=1;sum:=0;
while r<>d[i].right do
begin
if r<=d[i shl 1].right then i:=i shl 1
else
  begin
  inc(sum,d[i shl 1].key);
  i:=i shl 1 +1;
  end;
end;
inc(sum,d[i].key);
count:=sum;
end;

begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
{$ENDIF}
init;
fillchar(ans,sizeof(ans),0);
read(n);
for i:=1 to n do
  begin
  read(a,b);inc(a);
  inc(ans[count(a)]);
  inc(a,m-1);
  modify(a);
  end;
for i:=0 to n-1 do
  writeln(ans[i]);
{$IFNDEF ONLINE_JUDGE}
close(input);close(output);
{$ENDIF}
end.
Re: Why WA on TEST1!?
Posted by Ulyanov Maxim (KazanSU) 29 Oct 2005 23:50
But if I write
{$q+,r+,s+,t+}
const
m=32768;
type
key=record
left,key,right:word;
end;
var
ans:array[0..14999]of word;
d:array[1..2*m-1]of key;
n,i,a,b:word;

procedure init;
var
i:word;
begin
fillchar(d,sizeof(d),0);
d[1].left:=1;d[1].right:=m;
for i:=2 to 2*m-1 do
if not(odd(i)) then
begin
d[i].left:=d[i shr 1].left;
d[i].right:=(d[i shr 1].right-d[i shr 1].left)shr 1 +d[i].left;
end
else
begin
d[i].right:=d[i shr 1].right;
d[i].left:=d[i].right-(d[i shr 1].right-d[i shr 1].left)shr 1;
end;
end;

procedure modify(var i:word);
begin
repeat
inc(d[i].key);
i:=i shr 1;
until i=0;
end;

function count(var r:word):word;
var
sum:word;
begin
i:=1;sum:=0;
while r<>d[i].right do
begin
if r<=d[i shl 1].right then i:=i shl 1
else
begin
inc(sum,d[i shl 1].key);
i:=i shl 1 +1;
end;
end;
inc(sum,d[i].key);
count:=sum;
end;

begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
{$ENDIF}
init;
fillchar(ans,sizeof(ans),0);
read(n);
for i:=1 to n do
begin
read(a,b);inc(a);
inc(ans[count(a)]);
inc(a,m-1);
modify(a);
end;
writeln(1);
writeln(2);
writeln(1);
writeln(1);
writeln(0);
{$IFNDEF ONLINE_JUDGE}
close(input);close(output);
{$ENDIF}
end.
Test 1 is AC
If u test my previous solve you can see, that answers are equal.
What is THIS!!??