Codeforces 59 D. Team Arrangement

問題

3*n人が3人チームをn個作った。
それぞれの人には成績があり、同じ成績の人はいない。

チームの決め方は以下のようである。
まだチームに所属していない人のうち、成績が最も良い人が新しいチームのリーダーになる。
その人は、その人のつけている3*n-1人の優先順位の高い順に、まだチームに所属していない人を2人選ぶ。

それぞれのチームのメンバーおよび、各人の成績が与えられるとき、
k番目の人の優先順位として、ありえるもののうち、辞書順で最小のものを求めよ。

制約条件

n≦100000

方針

k番目の人が、チームリーダーでなければ優先順位は任意でよいので、
1 2 3 … nが辞書順で最小の列となる。

そうでないときは、{チームメイト}+{選ばれていない人}の配列と、
{既に選ばれた人}の配列を、マージソートの要領でマージしてやればよい。
すると、チームメイトが選ばれていない人の前に並び、なおかつ辞書順最小の列が得られる。

ソースコード

int n,k,a[300000];
int team[100000][3],where[300000];
int use[300000];

void run()
{
	cin>>n;
	rep(i,3*n)cin>>a[i], a[i]--;
	rep(i,n)rep(j,3)cin>>team[i][j], where[--team[i][j]]=i;
	cin>>k;
	k--;
	
	memset(use,0,sizeof(use));
	rep(i,3*n){
		if(a[i]==k){
			if(use[a[i]]){
				vi ans;
				rep(j,3*n)if(j!=a[i])ans.pb(j+1);
				rep(j,3*n-1)cout<<ans[j]<<(j==3*n-2?"\n":" ");
				return;
			}
			vi teammate,notselected,selected,ans(3*n-1);
			rep(j,3)if(team[where[a[i]]][j]!=a[i]){
				teammate.pb(team[where[a[i]]][j]+1);
				use[team[where[a[i]]][j]]=-1;
			}
			sort(all(teammate));
			
			rep(j,3*n){
				if(j==a[i]||use[j]<0)continue;
				if(use[j])selected.pb(j+1);
				else notselected.pb(j+1);
			}
			sort(all(selected)); sort(all(notselected));
			teammate.insert(teammate.end(),all(notselected));
			
			merge(all(teammate),all(selected),ans.begin());
			
			rep(j,3*n-1)cout<<ans[j]<<(j==3*n-2?"\n":" ");
			return;
		}
		if(!use[a[i]]){
			rep(j,3)use[team[where[a[i]]][j]]=1;
		}
	}
}