結果

問題 No.429 CupShuffle
ユーザー kichirb3kichirb3
提出日時 2018-03-25 22:52:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 2,147 bytes
コンパイル時間 845 ms
コンパイル使用メモリ 90,064 KB
実行使用メモリ 13,088 KB
最終ジャッジ日時 2023-09-07 12:12:08
合計ジャッジ時間 2,039 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 7 ms
4,380 KB
testcase_11 AC 55 ms
13,088 KB
testcase_12 AC 51 ms
13,012 KB
testcase_13 AC 57 ms
13,024 KB
testcase_14 AC 56 ms
13,008 KB
testcase_15 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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