B. Spongebob and Joke

1500
  • Quiz
  • AC
  • 感想
    • 問題理解に手間取りましたが、理解できれば簡単です
  • 問題把握
    • 長さMの配列Aがある（値域１～N）
    • 変換関数Fがある
    • AをFに通した長さMのBがある。Aに復元可能か？
  • 注意点
    • Fに重複な値があっても復元可能な場合がある
    • F = [1,2,3,3]
    • B = [1,2,1,2]
    • の場合、Aに逆変換できる
  • 解説
    • すべての値はFを通ってきているので、Fにない値をBが持っていたらImpossible
    • BからFの逆方向への変換が一意にできたら可能。途中で曖昧になるとAmbiguity
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    VI F(N);
    rep(i,N)cin>>F[i];

    VI B(M);
    rep(i,M)cin>>B[i];

    // Fを通したあとでありえる値たち
    set<ll> se;
    for(ll f : F)se.insert(f);

    // check B
    for(ll b : B){
      if(se.count(b)==0){
        p("Impossible");return 0;
      }
    }

    // 戻せる
    map<ll,VI> inv;
    rep(i,N){
      ll f = F[i];
      inv[F[i]].push_back(i+1);
    }

    VI A(M);
    rep(i,M){
      ll b = B[i];
      // bをaに戻す際に、候補が2つ以上あると曖昧
      if(inv[b].size()>1){
        p("Ambiguity");return 0;
      }
      A[i] = inv[B[i]][0];
    }
    p("Possible");
    print_vector(A);

    return 0;
}