結果

問題 No.429 CupShuffle
コンテスト
ユーザー kichirb3
提出日時 2018-03-25 22:52:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 2,147 bytes
コンパイル時間 822 ms
コンパイル使用メモリ 89,644 KB
実行使用メモリ 13,224 KB
最終ジャッジ日時 2024-06-25 06:17:13
合計ジャッジ時間 1,751 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

// No.429 CupShuffle
// https://yukicoder.me/problems/no/429
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <unordered_map>
using namespace std;

struct my_shuffle {
    int f;
    int t;
};


my_shuffle solve(vector<my_shuffle> &f_shuffle, vector<my_shuffle> &b_shuffle, unordered_map<int, int>& res, int N);

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int N, K, X;
    cin >> N >> K >> X;
    int a, b;
    vector<my_shuffle> f_shuffle; // ? ? 前までのシャッフル情報
    for (auto i = 1; i < X; ++i) {
        cin >> a >> b;
        f_shuffle.push_back(my_shuffle{a, b});
    }
    string s1, s2;
    cin >> s1 >> s2;
    vector<my_shuffle> b_shuffle; // ? ? 後のシャッフル情報
    for (auto i = X; i < K; ++i) {
        cin >> a >> b;
        b_shuffle.push_back(my_shuffle{a, b});
    }

    unordered_map<int, int> res; // 最終的なコップの配置
    for (auto i = 1; i <= N; ++i) {
        int t;
        cin >> t;
        res[i] = t;
    }

    my_shuffle ans = solve(f_shuffle, b_shuffle, res, N);
    cout << ans.f << " " << ans.t << endl;
}

my_shuffle solve(vector<my_shuffle> &f_shuffle, vector<my_shuffle> &b_shuffle, unordered_map<int, int>& res, int N) {
    unordered_map<int, int> f_status; // 最初から? ?までシャッフルしたコップの配置
    for (auto i = 1; i <= N; ++i)
        f_status[i] = i;        // コップが1, 2, 3, ...の順になるように初期化
    for (auto s: f_shuffle)
        swap(f_status[s.f], f_status[s.t]); // ? ?までシャッフル

    reverse(b_shuffle.begin(), b_shuffle.end()); // 最終状態から? ?まで逆順にシャッフルしたコップの配置
    for (auto s: b_shuffle)
        swap(res[s.f], res[s.t]);

    vector<int> ans;            // 違っている場所が2箇所あるはずなので、それを昇順に並べた物が答え
    for (auto i = 1; i <= N; ++i) {
        if (f_status[i] != res[i]) {
            ans.push_back(i);
            if (ans.size() >= 2)
                break;
        }
    }
    return my_shuffle{ans[0], ans[1]};
}
0