AtCoder Regular Contest 007 B - 迷子のCDケース

問題

問題文へ

CDケースをN枚、CDをN+1枚持っています。CDは0からNの連番がついていて、0がプレイヤーに入っていてケースはありません。他のCDは同じ番号のケースに入っています。

CDをM枚交換したリストが与えられます。最後のCDケースの状態を出力します。

制約

• 
• 

考えたこと

CDケースの状態を保存する配列を用意します。NとM共に100なので、毎回ケースを探索して交換先を探すとシンプルなコードで書けそうです。

が、今回は各CDがどこに入っているかも保存することにしてみました。

コード

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N, M;
  cin >> N >> M;

  vector<int> cd_case(N + 1);
  iota(cd_case.begin(), cd_case.end(), 0);
  vector<int> cd_pos(N + 1);
  iota(cd_pos.begin(), cd_pos.end(), 0);

  vector<int> set_list(M);
  rep(i, M) cin >> set_list[i];

  rep(i, M) {
    // 聞きたいCD(set_list[i])とプレイヤーのCD(cd_case[0])を入れ替える
    int cd_in_player = cd_case[0];
    swap(cd_case[cd_pos[set_list[i]]], cd_case[0]);
    cd_pos[cd_in_player] = cd_pos[set_list[i]];
    cd_pos[set_list[i]] = 0;
  }

  rep(i, N) cout << cd_case[i + 1] << endl;
  
  return 0;
}

解説を読んで

とくにありません。