当时用的是快排,但如果每次比完都快排的话,只能得50分。
实质上,只需要使用一次快排就可以了,比赛了,分别用a,b两个数组来储存胜利者和失败,当一轮比赛过后,再将这两个数组进行比较,合并为一个ans数组,可以大大节省时间。
ans[i,1]表示排名第i的选手的积分,ans[i,2]表示实力值,ans[i,3]表示他的编号。a储存胜利者,b储存失败者。
var n,r,q,k,l,m,i,j:longint;
win,lose,a:array[0..220000,1..3] of longint;
procedure qsort(x,y:longint);
var i,j,k,kk:longint;
begin
i:=x;
j:=y;
k:=a[(x+y) shr 1,2];
kk:=a[(x+y) shr 1,1];
while i<j dobegin
while(a[i,2]>k)or(a[i,2]=k)and(a[i,1]<kk)do inc(i);
while(a[j,2]<k)or(a[j,2]=k)and(a[j,1]>kk)do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
end;
if i<y thenqsort(i,y);
if j>x thenqsort(x,j);
end;
begin
readln(n,r,q);
for i:=1 to 2*n doread(a[i,2]);
for i:=1 to 2*n doread(a[i,3]);
for i:=1 to 2*n doa[i,1]:=i;
qsort(1,2*n);
for i:=1 to r do begin
for j:=1 to n do begin
ifa[2*j-1,3]>a[2*j,3] then begin
inc(a[2*j-1,2]);
win[j]:=a[2*j-1];
lose[j]:=a[2*j];
end elsebegin
inc(a[2*j,2]);
win[j]:=a[2*j];
lose[j]:=a[2*j-1];
end;
end;
k:=0;
l:=0;
m:=0;
while (k<n)or(l<n)do begin
if k+1>n thenbegin
for j:=l+1 to n do begin
inc(m);
a[m]:=lose[j];
end;
break;
end;
if l+1>n thenbegin
for j:=k+1 to n do begin
inc(m);
a[m]:=win[j];
end;
break;
end;
inc(m);
if(win[k+1,2]>lose[l+1,2])or(win[k+1,2]=lose[l+1,2])and(win[k+1,1]<lose[l+1,1])then begin
inc(k);
a[m]:=win[k];
end else begin
inc(l);
a[m]:=lose[l];;
end;
end;
end;
writeln(a[q,1]);
close(input);
close(output);
end.