yukicoder No.507 ゲーム大会(チーム決め)

問題はこちら
No.507 ゲーム大会(チーム決め) - yukicoder

K君以外の人のスコアを昇順にソートしておく
何点の人と組めばよいかを二分探索で求める。
X点の組がM位タイ以内に入れるというのは、X点より真に大きな点の組がM組未満であることと同値
これは尺取法によりO(N)で求まる。
二分探索が収束するまでO(logN)回やるので全体としてはO(NlogN)

a[1<<17];n,M,l,r,m,ll,rr,k;
c(int*p,int*q){return*p-*q;}
main(){
	scanf("%d%d",&n,&M);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	qsort(a+1,n-1,4,c);
	l=0;r=n;
	while(r-l>1){
		//半開区間(l,r]での二分探索
		//（rは解なしのときと対応）
		m=(l+r)/2;
		ll=1;rr=n-1;k=0;
		while(ll<rr){
			//尺取法
			//得点が高い人は、できるだけ低い点の人と組む
			if(ll==m)ll++;
			else if(rr==m)rr--;
			else if(a[ll]+a[rr]>a[0]+a[m])k++,ll++,rr--;
			else ll++;
		}
		if(k<M)r=m;
		else l=m;
	}
	printf("%d",r==n?-1:a[r]);
}

まずはこの部分を縮める

if(ll==m)ll++;
else if(rr==m)rr--;
else if(a[ll]+a[rr]>a[0]+a[m])k++,ll++,rr--;
else ll++;

rr==m?rr--:
ll==m?ll--:
a[ll]+a[rr]>a[0]+a[m]?k++,ll++,rr--:ll++;

rr==m?rr--:
(ll!=m&&a[ll]+a[rr]>a[0]+a[m]?k++,rr--:0,ll++);

rr-m?ll-m&&a[ll]+a[rr]>a[0]+a[m]?k++,rr--:0,ll++:rr--;

読み込みを全部aにまとめる。indexのズレに気をつけながら縮めると

a[1<<17],p,q,l,r,m;
c(int*p,int*q){m=*p-*q;}
main(k){
	for(l=2;~scanf("%d",a+r);r++);
	for(qsort(a+3,r-3,4,c);r-l>1;k<a[1]?r=m:(l=m))
		for(m=l+r>>1,p=3,q=*a+1,k=0;p<q;q-m?p-m&&a[p]+a[q]>a[2]+a[m]?q--,k++:0,p++:q--);
	printf("%d",a[r]?:-1);
}

ぐっと睨んで、一番短くなるようにindexをずらす

a[1<<17],p,q,l,r,m;c(int*p,int*q){m=*p-*q;}main(k){for(l=2;~scanf("%d",a+r);r++);for(qsort(a+3,r-3,4,c);r-l>1;k<a[1]?r=m:(l=m))for(m=l+r>>1,p=3,q=*a+1,k=0;p<q;q-m?p-m&&a[p]+a[q]>a[2]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);}
a[1<<17],p,q,k,r,m;c(int*p,int*q){m=*p-*q;}main(l){for(;~scanf("%d",a-1+r);r++);for(qsort(a+2,r-3,4,c);r-l>1;k<*a?r=m:(l=m))for(m=l+r>>1,p=2,q=a[-1],k=0;p<q;q-m?p-m&&a[p]+a[q]>a[1]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);}
a[1<<17],p,q,l,r,m;c(int*p,int*q){m=*p-*q;}main(k){for(;~scanf("%d",a-2+r);r++);for(qsort(a+1,r-3,4,c);r-l>1;k<a[-1]?r=m:(l=m))for(m=l+r>>1,p=1,q=a[-2],k=0;p<q;q-m?p-m&&a[p]+a[q]>*a+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);}
a[1<<17],p,q,k,r,m;c(int*p,int*q){m=*p-*q;}main(l){for(;~scanf("%d",a-3+r);r++);for(qsort(a,r-3,4,c);r+l>1;k<a[-2]?r=m:(l=-m))for(m=r-l>>1,q=a[-3],p=k=0;p<q;q-m?p-m&&a[p]+a[q]>a[-1]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);}

ということで結局一番短くなるのは上から2番目の

a[1<<17],p,q,k,r,m;
c(int*p,int*q){m=*p-*q;}
main(l){
	for(;~scanf("%d",a-1+r);r++);
	for(qsort(a+2,r-3,4,c);r-l>1;k<*a?r=m:(l=m))
		for(m=l+r>>1,p=2,q=a[-1],k=0;p<q;q-m?p-m&&a[p]+a[q]>a[1]+a[m]?q--,k++:0,p++:q--);
	printf("%d",a[r]?:-1);
}

228B