CupShuffle [yukicoder 429]

問題

http://yukicoder.me/problems/no/429

N個のコップがあり、K回2つのコップを入れ替える作業を行うがが、
X回目の作業で入れ替えたコップの位置だけ分からないので、答えよ。

入れ替え作業の流れは以下の通り。

• 最初、位置iにはコップiがある
• i回目の交換ではA[i]の位置とB[i]の位置のコップを入れ替える
• 最終的に、位置iにはコップC[i]がある

2 <= N <= 10^5
1 <= K <= 10^5

考察

1. X回目の作業を知りたいが、何が分かれば分かりそうか
2. X回目の作業前と作業後の状態が分かれば、何と何を入れ替えたかが分かる

3. X回目の作業前は、位置iにコップiがある状態から1～X-1回目の作業をシミュレートすれば分かる
4. X回目の作業後は、位置iにコップC[i]がある状態からK回目の作業から、X+1回目の作業まで、作業順を遡るようにシミュレートすれば分かる
5. あとは、これの差を考えれば答え

実装

http://yukicoder.me/submissions/120916

#define rrep(i,a,b) for(int i=a;i>=b;i--)
int N, K, X;
int A[101010], B[101010];
int C[101010];
int buf[101010];
//-----------------------------------------------------------------
int main() {
	cin >> N >> K >> X;
	X--;
	rep(i, 0, K) {
		if (i == X) {
			string s;
			cin >> s;
			cin >> s;
			A[i] = B[i] = -1;
		}
		else {
			cin >> A[i] >> B[i];
			A[i]--;
			B[i]--;
		}
	}
	rep(i, 0, N) cin >> C[i];

	rep(i, 0, N) buf[i] = i + 1;
	rep(i, 0, X) {
		swap(buf[A[i]], buf[B[i]]);
	}

	rrep(i, K - 1, X + 1) {
		swap(C[A[i]], C[B[i]]);
	}

	set<int> ans;
	rep(i, 0, N) if (buf[i] != C[i]) ans.insert(i + 1);
	
	for (int i : ans) cout << i << " ";
	cout << endl;
}