CSAcademy Round #13 : C. Balanced Min Pairing

全体的に手間取りすぎた。
https://csacademy.com/contest/round-13/#task/balanced-min-pairing

問題

N(偶数)要素の２つの整数列A,Bがある。
Aの要素とBの要素を1つずつ合わせた対をN個作る。
その際以下のような組み合わせが構築せよ。

• A,Bの各要素は1回ずつ使われる。
• 対の２値の数値は異なっている。
• Aから抜き出した要素の方が小さい対と、Bから抜き出した要素の方が小さい対と半々である。

解法

A,Bそれぞれソートし、Aの下半分とBの上半分、Aの上半分とBの下半分を組み合わせればよい。
前者はAの方が小さく、後者はBの方が小さいことを判定する。

それ以外にも対を構築する方法はあるが、小さい方の要素をより小さく、大きい方の要素をより大きくしても問題の条件を満たさなくなることはない。

int T;
int N;
int R[50505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> AA;
		vector<pair<int,int>> BB;
		FOR(i,N) cin>>x, AA.push_back({x,i});
		FOR(i,N) cin>>x, BB.push_back({x,i});
		sort(ALL(AA));
		sort(ALL(BB));
		
		FOR(i,N/2) {
			if(AA[i].first>=BB[i+N/2].first) {
				_P("-1\n");
				goto out;
			}
			if(AA[i+N/2].first<=BB[i].first) {
				_P("-1\n");
				goto out;
			}
			R[AA[i].second]=BB[i+N/2].second+1;
			R[AA[i+N/2].second]=BB[i].second+1;
		}
		
		FOR(i,N) _P("%d%c",R[i],(i==N-1)?'\n':' ');
		out:
		;
	}
}

まとめ

本番考えすぎて手間取った。