yukicoder : No.2771 Personal Space

これは割と素直。
https://yukicoder.me/problems/no/2771

問題

N個の椅子が順に並んでおり、1人目はM番目の椅子に座った。
以降の人は、最寄の人への距離が最大となる椅子に座るとする。

N人が順に椅子に座るとき、各席に座るのは何番目に座ろうとした人か。

解法

愚直に、各席から最寄りの人への距離を算出しその最大となるものを選べばよい。
各椅子で最寄りの人への距離が変わるのはO(logN)回程度なのでこれで足りる。

int T;
int N,M;
int D[303030];
int ret[303030];
set<int> Ss[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		set<int> S;
		M--;
		ret[M]=0;
		S.insert(M);
		S.insert(-1<<20);
		S.insert(1<<20);
		FOR(i,N) {
			D[i]=abs(i-M);
			Ss[D[i]].insert(i);
		}
		int nex=1;
		for(i=N;i>=1;i--) while(Ss[i].size()) {
			x=*Ss[i].begin();
			Ss[i].erase(x);
			ret[x]=nex++;
			int ne=*S.lower_bound(x);
			int pr=*prev(S.lower_bound(x));
			S.insert(x);
			for(j=max(0,pr+1);j<min(N,ne);j++) if(j!=x) {
				Ss[D[j]].erase(j);
				if(j<x) D[j]=min(abs(j-pr),abs(j-x));
				if(j>x) D[j]=min(abs(j-ne),abs(j-x));
				if(D[j]) Ss[D[j]].insert(j);
			}
		}
		
		FOR(i,N) cout<<ret[i]+1<<" ";
		cout<<endl;
		
	}
}

まとめ

これNが大きいケースをどこかで見たような気がするが…。