记录编号	40676	评测结果	AAAAAA
题目名称	[暑假培训2012] 黑叔	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	Pascal	运行时间	0.039 s
提交时间	2012-07-18 16:11:39	内存使用	2.68 MiB

var
n,i,j,k,time,q:longint;
t:array[0..10001]of longint;
d:array[0..10001]of longint;
c:array[0..10001]of string;
procedure qsort(l,r:longint);
var
x,y,z,zz:longint;
zzz:string;
begin
x:=l;
y:=r;
z:=t[(x+y)div 2];
repeat
while t[x]<z do inc(x);
while t[y]>z do dec(y);
if x<=y then
 begin
  zz:=t[x];
  t[x]:=t[y];
  t[y]:=zz;
  zzz:=c[x];
  c[x]:=c[y];
  c[y]:=zzz;
  zz:=d[x];
  d[x]:=d[y];
  d[y]:=zz;

  inc(x);
  dec(y);
 end;
until x>y;
if x<r then qsort(x,r);
if l<y then qsort(l,y);
end;

procedure qsortpart(l,r:longint);
var
x,y,zz:longint;
z,zzz:string;
begin
x:=l;
y:=r;
z:=c[(x+y)div 2];
repeat
while c[x]<z do inc(x);
while c[y]>z do dec(y);
if x<=y then
 begin
  zz:=t[x];
  t[x]:=t[y];
  t[y]:=zz;
  zzz:=c[x];
  c[x]:=c[y];
  c[y]:=zzz;
  zz:=d[x];
  d[x]:=d[y];
  d[y]:=zz;

  inc(x);
  dec(y);
 end;
until x>y;
if x<r then qsortpart(x,r);
if l<y then qsortpart(l,y);
end;

procedure switchin(l,r:longint);
var
ii,jj,kk:longint;
begin
if t[l]<t[l+1] then exit;
if t[l]>t[r] then
 begin
  kk:=t[l];
  for ii:=1 to r-1 do t[ii]:=t[ii+1];
  t[r]:=kk;
  exit;
 end;
for ii:=2 to r-1 do
 if (t[ii]<=t[l])and(t[ii+1]>t[l]) then
  begin
   kk:=t[l];
   for jj:=2 to ii do t[jj-1]:=t[jj];
   t[ii]:=kk;
   exit;
  end;

end;

begin
assign(input,'hey.in');reset(input);
assign(output,'hey.out');rewrite(output);
read(n);
for i:=1 to n do
 begin
  read(t[i]);
  read(c[i]);
  j:=length(c[i]);
  k:=1;
  while (ord(c[i][j])>=48)and(ord(c[i][j])<=57) do
   begin
    d[i]:=d[i]+(ord(c[i][j])-48)*k;
    k:=k*10;
    dec(j);
   end;
  k:=length(c[i])-j+1;
  delete(c[i],j,k);
  delete(c[i],1,1);
 end;
qsort(1,n);
i:=1;
while i<n do
 begin
  j:=i;
  while t[j+1]=t[i] do inc(j);
  if i<j then qsortpart(i,j);
  i:=j+1;
 end;

time:=0;
i:=1;
t[0]:=t[1];
t[n+1]:=maxlongint;

while i<=n do
begin
  if (time<=t[i])and(t[i]<>t[i+1]) then
   begin
    writeln(c[i],' went out at time ',t[i]);
    time:=t[i]+d[i];
    inc(i);
   end;
  if (time<=t[i])and(t[i]=t[i+1]) then
   begin
    j:=i+1;
    while t[j+1]=t[i] do inc(j);
    switchin(i,j);
    writeln(c[i],' went out at time ',t[i]);
    time:=t[i]+d[i];
    inc(i);
   end;

  if time>t[i] then
   begin
    t[i]:=time;
    j:=i;
    while t[j+1]<=time do
     begin
      inc(j);
      t[j]:=time;
     end;
   end;

end;
close(input);
close(output);
end.