Artsem and Saunders - codeforces#397D
where
思考
此題目中兩個條件為：
從第一個式子，或者是將 f(x) 的 x 指向 f(x) 畫成一張有向圖，再將 h(x)、g(x) 用上面的條件加點加邊上去，會發現有 m 個點經由 h 這個函式指向 f(x)，而 m 則為 f(x) 相異數的數量。
因此將 f(x) 相異數填上 h 之後，再利用第一個式子產出 g （因該式為 [n] ），由第二個式子確認即可。
Code
#include <bits/stdc++.h>
using namespace std;
int T, N, M, Q, F[100005], G[100005], H[100005], Hi[100005];
//Hi為H之inverse
void ini(void){
M = 0;
scanf("%d", &N);
for(int i = 1; i <= N; i++){
scanf("%d", F + i);
if(!G[ F[i] ]){
//利用目前沒在用的G來當確認重複f(x)用
G[ F[i] ] = 1;
H[ ++M ] = F[i];
Hi[ F[i] ] = M;
}
}
}
int sol(void){
int i;
memset(G, 0, sizeof(G));
//h( g(x) ) = f(x)
for(i = 1; i <= N; i++){
G[i] = Hi[ F[i] ];
}
//g( h(x) ) = x
for(i = 1; i <= M; i++){
if(G[H[i]] != i){
printf("-1\n");
return 0;
}
}
//output
printf("%d\n", M);
for(i = 1; i <= N; i++){
printf("%d", G[i]);
if(i != N) printf(" ");
else printf("\n");
}
for(i = 1; i <= M; i++){
printf("%d", H[i]);
if(i != M) printf(" ");
else printf("\n");
}
return 0;
}
int main(void){
int i, j;
ini();
sol();
}