Codeforces #162 Div2. C. Escape from Stones

さて次の問題。Div1 Aと同じ。
http://codeforces.com/contest/265/problem/C

最初リスは[0,1]の領域を保持している。
リスの保持している領域の真ん中に岩が落ちてくるので、リスは領域の左半分か右半分に逃げるため保持領域が半分になる。
リスの逃げた履歴が与えられたとき、岩の並び順を答える。

一度岩の左か右に逃げると、以降の岩はすべてその左または右に行く。
よって、逆に逃げた順を逆にたどると、リスが左に逃げたのならその時の岩は以降の岩の右側にあることにある。
よって逃げた順を逆順にたどりつつ、左右に岩を追加していけばO(N)で解ける。

char str[1000001];
int id[2000001];
int L;

void solve() {
	int f,i,j,k,l,r;
	int res;
	
	GETs(str);
	MINUS(id);
	L=strlen(str);
	l=r=1000000;
	id[l]=L;
	
	for(i=L-2;i>=0;i--) {
		if(str[i]=='l') id[++r]=i+1;
		else id[--l]=i+1;
	}
	
	FOR(i,2000001) if(id[i]>=0) _P("%d\n",id[i]);
	
	return;
}

まとめ

問題の設定が割と無理ある気がするけど…。
問題自体は面白いね。