Codeforces #887 : Div1 B. Imbalanced Arrays

Bまでは簡単だったんだけどね…。
https://codeforces.com/contest/1852/problem/B

問題

N要素の非負整数列Aが与えられる。
以下を満たすBが存在するか。するなら一例を示せ。

• Bは-N以上N以下の0でない整数値を取るN要素の整数列。
• Bのうち足して0になる2要素は存在しない。
• A[i]は、B[i]+B[j]が正となるjの個数とする。

解法

• Aが空でない場合、A[i]=Nな要素かA[i]=0な要素を見つけよう。同じ値は複数あってもよいが、Nになるものと0になるものが両方あってはならない
  • A[i]=Nな要素がある場合、B[i]=Nとする。
  • A[i]=0な要素がある場合、B[i]=-Nとする。
• 上記に該当するiを取り除き、その分Nを減らして、残された要素に対し同様に繰り返すとよい。

int T,N,A[101010],B[101010];
vector<int> C[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+1) C[i].clear();
		FOR(i,N) {
			B[i]=-1<<30;
			cin>>A[i];
			C[A[i]].push_back(i);
		}
		int L=0,R=N;
		while(L<R) {
			if(C[L].empty()==C[R].empty()) break;
			if(C[L].empty()) {
				FORR(c,C[R]) B[c]=R-L;
				L+=C[R].size();
				C[R].clear();
			}
			else if(C[R].empty()) {
				FORR(c,C[L]) B[c]=L-R;
				R-=C[L].size();
				C[L].clear();
			}
		}
		FOR(i,N) if(B[i]==-1<<30) break;
		if(i<N) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
			FOR(i,N) cout<<B[i]<<" ";
			cout<<endl;
		}
			
	}
}

まとめ

B[i]+B[j]が非0ってところでNか-Nを積極的に使うことを思いついた気がする。