记录编号	77614	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]瑞士轮	最终得分	100
用户昵称	gungnir	是否通过	通过
代码语言	Pascal	运行时间	2.704 s
提交时间	2013-11-02 09:46:32	内存使用	13.90 MiB

type atype=record s,t,w:longint; end;
var
a,buffer,win,lost:array[0..300000]of atype;
n,rr,q,nn,i,j,head,l,r:longint;

procedure qsort(l,r:longint);
var i,j,mid1,mid2:longint; temp:atype;
begin
i:=l; j:=r;
mid1:=a[(l+r) div 2].s;
mid2:=a[(l+r)div 2 ].t;
   while i<=j do
   begin
     while(a[i].s>mid1)or((a[i].s=mid1)and(a[i].t<mid2))
     do inc(i);
     while(a[j].s<mid1)or((a[j].s=mid1)and(a[j].t>mid2))
     do dec(j);
     if i<=j then
     begin
     temp:=a[i]; a[i]:=a[j]; a[j]:=temp;
     inc(i); dec(j);
     end;
   end;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

begin
assign(input,'swiss.in');reset(input);
assign(output,'swiss.out');rewrite(output);
readln(n,rr,q);
nn:=n*2;
for i:=1 to nn do read(a[i].s);
for i:=1 to nn do read(a[i].w);
for i:=1 to nn do a[i].t:=i;
qsort(1,nn);
head:=0;
repeat
fillchar(win,sizeof(win),0);
fillchar(lost,sizeof(lost),0);
fillchar(buffer,sizeof(buffer),0);
inc(head);
for i:=1 to n do
if(a[2*i].w>a[2*i-1].w)then
begin
win[i]:=a[2*i]; lost[i]:=a[2*i-1]; inc(win[i].s);
end
else
begin
win[i]:=a[2*i-1]; lost[i]:=a[2*i]; inc(win[i].s);
end;
l:=1; r:=1;
while(l<=n)or(r<=n)do
begin
if(win[l].s>lost[r].s)or
(win[l].s=lost[r].s)and(win[l].t<lost[r].t)and(l<=n)
then begin buffer[l+r-1]:=win[l]; inc(l); end
else begin buffer[l+r-1]:=lost[r]; inc(r); end;
end;
a:=buffer;
until head=rr;

writeln(a[q].t);
{for i:=1 to nn do writeln(a[i].s,' ',a[i].t); }

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