Codeforces #270 Div1 C. Design Tutorial : Make It Nondeterministic

CF270に参加。
ABCDだけさっさと解いて、後はHack…を狙ったがろくに稼げず。
とはいえABCD早解きのおかげでレートはHighest更新した。
http://codeforces.com/contest/472/problem/C

問題

N人の姓名および1～NのPermutationが与えられる。
N人をPermutationの順に並べ替えたとき、N人それぞれを苗字または名前のいずれかで呼んだら、それが昇順になるような可能性はあるかどうか答えよ。

解法

1人目を姓名のうち辞書順で小さい方からスタートする。
あとは(i-1)番目の人の呼び方が確定したら、かつi番目の人を姓と名のうち(i-1)番の呼び方より辞書順で後であり、かつ小さい方を選択していけばよい。
姓名どちらを選択しても(i-1)番目の呼び方より小さいなら、問題の条件を満たす可能性は無し。

int N;
string F[100010],S[100010];
int P[100010];
string cur;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>F[i]>>S[i];
		if(F[i]>S[i]) swap(F[i],S[i]);
	}
	FOR(i,N) {
		cin>>x;
		x--;
		if(F[x]>cur) cur=F[x];
		else if(S[x]>cur) cur=S[x];
		else return _P("NO\n");
	}
	return _P("YES\n");
}

まとめ

ここらへんはあっさり。