結果

問題 No.429 CupShuffle
ユーザー airis
提出日時 2016-10-02 23:20:37
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 122 ms
コード長 1,266 Byte
コンパイル時間 950 ms
使用メモリ 8,916 KB
最終ジャッジ日時 2019-07-13 09:45:45

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 3 ms
6,872 KB
case2.txt AC 3 ms
6,868 KB
case3.txt AC 2 ms
6,872 KB
case4.txt AC 2 ms
6,868 KB
case5.txt AC 3 ms
6,868 KB
case6.txt AC 3 ms
6,868 KB
case7.txt AC 3 ms
6,868 KB
case8.txt AC 3 ms
8,916 KB
case9.txt AC 3 ms
6,868 KB
case10.txt AC 4 ms
6,872 KB
case11.txt AC 13 ms
8,912 KB
case12.txt AC 121 ms
6,872 KB
case13.txt AC 110 ms
6,868 KB
case14.txt AC 119 ms
6,872 KB
case15.txt AC 122 ms
6,868 KB
case16.txt AC 2 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define EPS (1e-14)
#define _PA(x,N) rep(i,N){cout<<x[i]<<" ";}cout<<endl;
#define _PA2(x,H,W) rep(i,(H)){rep(j,(W)){cout<<x[i][j]<<" ";}cout<<endl;}

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef complex<double> Complex;
typedef vector< vector<int> > Mat;

int N, K, X;
int A[100005], B[100005];
int C[100005];

int init[100005];

vector<int> ans;

void solve() {
	for (int i = 0; i < N; i++) {
		init[i] = i + 1;
	}
	// forward
	for (int i = 0; i < X - 1; i++) {
		int a = A[i] - 1;
		int b = B[i] - 1;
		swap(init[a], init[b]);
	}

	// backward
	for (int i = K - 1; i > X - 1; i--) {
		int a = A[i] - 1;
		int b = B[i] - 1;
		swap(C[a], C[b]);
	}

	//_PA(init, N);
	//_PA(C, N);

	for (int i = 0; i < N; i++) {
		if (init[i] != C[i]) {
			ans.push_back(i + 1);
		}
	}
	//cout << ans.size() << endl;

	printf("%d %d\n", ans[0], ans[1]);

}

int main() {
	cin >> N >> K >> X;
	for (int i = 0; i < K; i++) {
		if (i != X - 1) {
			cin >> A[i] >> B[i];
		} else {
			char a, b;
			cin >> a >> b;
		}
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	solve();
	return 0;
}


0