代码

#include "kth.h"
#include<iostream>
using namespace std;
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int query_kth(int n_a, int n_b, int n_c, int k)
{
#define qra()  if(l[0]>r[0])m[0]=l[0];else m[0]=(l[0]+r[0])>>1,v[0]=get_a(m[0])
#define qrb()  if(l[1]>r[1])m[1]=l[1];else m[1]=(l[1]+r[1])>>1,v[1]=get_b(m[1])
#define qrc()  if(l[2]>r[2])m[2]=l[2];else m[2]=(l[2]+r[2])>>1,v[2]=get_c(m[2])
	int l[3]={0,0,0};
	int r[3]={n_a-1,n_b-1,n_c-1};
	int m[3]={},v[3]={};
	qra();qrb();qrc();
	int lastans=-1;
	while(l[0]<=r[0]||l[1]<=r[1]||l[2]<=r[2])
	{
		int rk=m[0]+m[1]+m[2]+1;
		if(rk<=k)
		{
			int mn=2147483647;
			if(l[0]<=r[0])mn=min(mn,v[0]);
			if(l[1]<=r[1])mn=min(mn,v[1]);
			if(l[2]<=r[2])mn=min(mn,v[2]);
			if(l[0]<=r[0]&&v[0]==mn)
			{
				lastans=max(lastans,v[0]);l[0]=m[0]+1;qra();
			}
			else if(l[1]<=r[1]&&v[1]==mn)
			{
				lastans=max(lastans,v[1]);l[1]=m[1]+1;qrb();
			}
			else if(l[2]<=r[2]&&v[2]==mn)
			{
				lastans=max(lastans,v[2]);l[2]=m[2]+1;qrc();
			}
		}
		else
		{
			int mx=-2147483647;
			if(l[0]<=r[0])mx=max(mx,v[0]);
			if(l[1]<=r[1])mx=max(mx,v[1]);
			if(l[2]<=r[2])mx=max(mx,v[2]);
			if(l[0]<=r[0]&&v[0]==mx)
			{
				r[0]=m[0]-1;qra();
			}
			else if(l[1]<=r[1]&&v[1]==mx)
			{
				r[1]=m[1]-1;qrb();
			}
			else if(l[2]<=r[2]&&v[2]==mx)
			{
				r[2]=m[2]-1;qrc();
			}
		}
	}
	return lastans;
}

评测结果