#974324 (C++17) No.2732 Similar Permutations

提出ソース

結果

問題	No.2732 Similar Permutations
ユーザー	Today03
提出日時	2024-04-19 22:40:47
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	106 ms / 2,000 ms
コード長	7,101 bytes
コンパイル時間	4,211 ms
コンパイル使用メモリ	226,308 KB
実行使用メモリ	8,576 KB
最終ジャッジ日時	2024-04-19 22:41:18
合計ジャッジ時間	20,688 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	29 ms 5,376 KB
testcase_03	AC	55 ms 5,376 KB
testcase_04	AC	18 ms 5,376 KB
testcase_05	AC	15 ms 5,376 KB
testcase_06	AC	7 ms 5,376 KB
testcase_07	AC	39 ms 5,376 KB
testcase_08	AC	23 ms 5,376 KB
testcase_09	AC	11 ms 5,376 KB
testcase_10	AC	96 ms 8,576 KB
testcase_11	AC	10 ms 5,376 KB
testcase_12	AC	106 ms 5,504 KB
testcase_13	AC	97 ms 5,632 KB
testcase_14	AC	98 ms 5,632 KB
testcase_15	AC	99 ms 5,632 KB
testcase_16	AC	72 ms 5,504 KB
testcase_17	AC	71 ms 5,504 KB
testcase_18	AC	92 ms 6,272 KB
testcase_19	AC	95 ms 5,760 KB
testcase_20	AC	105 ms 6,272 KB
testcase_21	AC	96 ms 5,504 KB
testcase_22	AC	54 ms 5,376 KB
testcase_23	AC	97 ms 6,400 KB
testcase_24	AC	56 ms 5,376 KB
testcase_25	AC	95 ms 6,528 KB
testcase_26	AC	81 ms 5,376 KB
testcase_27	AC	106 ms 6,528 KB
testcase_28	AC	77 ms 5,376 KB
testcase_29	AC	94 ms 6,528 KB
testcase_30	AC	66 ms 5,376 KB
testcase_31	AC	106 ms 5,504 KB
testcase_32	AC	87 ms 5,376 KB
testcase_33	AC	100 ms 5,632 KB
testcase_34	AC	63 ms 5,376 KB
testcase_35	AC	97 ms 5,504 KB
testcase_36	AC	87 ms 5,376 KB
testcase_37	AC	99 ms 5,760 KB
testcase_38	AC	85 ms 5,376 KB
testcase_39	AC	99 ms 5,632 KB
testcase_40	AC	77 ms 5,376 KB
testcase_41	AC	95 ms 5,504 KB
testcase_42	AC	71 ms 5,376 KB
testcase_43	AC	94 ms 5,504 KB
testcase_44	AC	51 ms 5,376 KB
testcase_45	AC	96 ms 5,760 KB
testcase_46	AC	87 ms 5,376 KB
testcase_47	AC	94 ms 5,632 KB
testcase_48	AC	56 ms 5,376 KB
testcase_49	AC	87 ms 5,632 KB
testcase_50	AC	57 ms 5,376 KB
testcase_51	AC	90 ms 5,632 KB
testcase_52	AC	74 ms 5,376 KB
testcase_53	AC	94 ms 7,168 KB
testcase_54	AC	105 ms 6,400 KB
testcase_55	AC	96 ms 5,760 KB
testcase_56	AC	105 ms 5,632 KB
testcase_57	AC	50 ms 5,632 KB
testcase_58	AC	72 ms 6,656 KB
testcase_59	AC	66 ms 5,760 KB
testcase_60	AC	57 ms 5,376 KB
testcase_61	AC	47 ms 5,376 KB
testcase_62	AC	79 ms 6,400 KB
testcase_63	AC	2 ms 5,376 KB
testcase_64	AC	2 ms 5,376 KB
testcase_65	AC	2 ms 5,376 KB
testcase_66	AC	2 ms 5,376 KB
testcase_67	AC	2 ms 5,376 KB
testcase_68	AC	2 ms 5,376 KB
testcase_69	AC	1 ms 5,376 KB
testcase_70	AC	2 ms 5,376 KB
testcase_71	AC	2 ms 5,376 KB
testcase_72	AC	2 ms 5,376 KB
testcase_73	AC	2 ms 5,376 KB
testcase_74	AC	2 ms 5,376 KB
testcase_75	AC	3 ms 5,376 KB
testcase_76	AC	2 ms 5,376 KB
testcase_77	AC	2 ms 5,376 KB
testcase_78	AC	2 ms 5,376 KB
testcase_79	AC	2 ms 5,376 KB
testcase_80	AC	2 ms 5,376 KB
testcase_81	AC	1 ms 5,376 KB
testcase_82	AC	1 ms 5,376 KB
testcase_83	AC	1 ms 5,376 KB
testcase_84	AC	2 ms 5,376 KB
testcase_85	AC	2 ms 5,376 KB
testcase_86	AC	2 ms 5,376 KB
testcase_87	AC	1 ms 5,376 KB
testcase_88	AC	1 ms 5,376 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	2 ms 5,376 KB
testcase_91	AC	2 ms 5,376 KB
testcase_92	AC	2 ms 5,376 KB
testcase_93	AC	1 ms 5,376 KB
testcase_94	AC	2 ms 5,376 KB
testcase_95	AC	2 ms 5,376 KB
testcase_96	AC	2 ms 5,376 KB
testcase_97	AC	2 ms 5,376 KB
testcase_98	AC	2 ms 5,376 KB
testcase_99	AC	1 ms 5,376 KB
testcase_100	AC	2 ms 5,376 KB
testcase_101	AC	1 ms 5,376 KB
testcase_102	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

namespace random_generator {
    mt19937_64 generate;
    void init() {
        random_device seed_gen;
        generate = mt19937_64(seed_gen());
    }
    template <typename T>
    T random_int(T x) {
        assert(x > 0);
        return generate() % x;
    }
    template <typename T>
    T random_int(T x, T y) {
        assert(x < y);
        return x + generate() % (y - x);
    }
    template <typename T>
    T get_elememt(vector<T>& a) {
        const int n = a.size();
        int idx = random_int(0, n);
        swap(a[n - 1], a[idx]);
        int ret = a.back();
        a.pop_back();
        return ret;
    }
    template <typename T>
    vector<T> random_array_int(int n, T lo, T hi, bool no_dup = false) {
        vector<T> ret(n);
        if (!no_dup) {
            for (int i = 0; i < n; i++) {
                ret[i] = random_int(lo, hi);
            }
        } else {
            set<T> st;
            for (int i = 0; i < n; i++) {
                int r = random_int(lo, hi);
                while (st.count(r)) {
                    r = random_int(lo, hi);
                }
                ret[i] = r;
                st.insert(r);
            }
        }
        return ret;
    }
    string random_alphabet(int n, bool lower = true) {
        string ret;
        for (int i = 0; i < n; i++) {
            int idx = random_int(26);
            ret.push_back(char((lower ? 'a' : 'A') + idx));
        }
        return ret;
    }
    string random_string(int n, string s) {
        string ret;
        int m = s.size();
        for (int i = 0; i < n; i++) {
            int idx = random_int(m);
            ret.push_back(s[idx]);
        }
        return ret;
    }
    template <typename T>
    vector<vector<T>> random_array_2D(int h, int w, T lo, T hi) {
        vector<vector<T>> ret(h, vector<T>(w));
        for (int i = 0; i < h; i++) {
            ret[i] = random_array_int(w, lo, hi);
        }
        return ret;
    }
    vector<string> random_alphabet_2D(int h, int w, bool lower = true) {
        vector<string> ret(h);
        for (int i = 0; i < h; i++) {
            ret[i] = random_alphabet(w, lower);
        }
        return ret;
    }
    vector<pair<int, int>> random_tree(int n) {
        vector<int> a = random_array_int<int>(n - 2, 1, n + 1);
        vector<int> d(n + 1);
        for (int i = 0; i < n - 2; i++) {
            d[a[i]]++;
        }
        for (int i = 1; i <= n; i++) {
            d[i]++;
        }
        vector<pair<int, int>> ret;
        set<int> pq;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                pq.insert(i);
            }
        }
        for (int i = 0; i < n - 2; i++) {
            int v = (*pq.begin());
            pq.erase(v);
            ret.push_back(make_pair(v, a[i]));
            d[v]--;
            d[a[i]]--;
            if (d[a[i]] == 1) {
                pq.insert(a[i]);
            } else if (d[a[i]] == 0) {
                pq.erase(a[i]);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                for (int j = i + 1; j <= n; j++) {
                    if (d[j] == 1) {
                        ret.push_back(make_pair(i, j));
                        break;
                    }
                }
                break;
            }
        }
        return ret;
    }
    vector<pair<int, int>> random_bintree(int n) {
        vector<pair<int, int>> ret;
        vector<ll> roots = {random_int(1, n + 1)};
        vector<ll> leaves;
        for (int i = 1; i <= n; i++) {
            if (i != roots.back()) {
                leaves.push_back(i);
            }
        }
        while (!leaves.empty()) {
            int root = get_elememt(roots);
            int leaf = get_elememt(leaves);
            ret.push_back(make_pair(root, leaf));
            roots.push_back(leaf);
            if (!leaves.empty()) {
                int leaf = get_elememt(leaves);
                ret.push_back(make_pair(root, leaf));
                roots.push_back(leaf);
            }
        }
        return ret;
    }
    vector<pair<int, int>> random_undigraph(int n, int m, bool connected = true) {
        vector<pair<int, int>> edges;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.push_back(make_pair(i + 1, j + 1));
            }
        }
        int ed = edges.size();
        if (!connected) {
            vector<pair<int, int>> ret;
            vector<int> idxs = random_array_int<int>(m, 0, ed, true);
            for (int idx : idxs) {
                ret.push_back(edges[idx]);
            }
            return ret;
        } else {
            vector<pair<int, int>> ret;
            while (true) {
                ret.clear();
                vector<int> idxs = random_array_int<int>(m, 0, ed, true);
                vector<int> parent(n);
                vector<vector<int>> sets(n);
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    sets[i].push_back(i);
                }
                for (int idx : idxs) {
                    ret.push_back(edges[idx]);
                    auto [a, b] = edges[idx];
                    a--;
                    b--;
                    if (parent[a] != parent[b]) {
                        if (sets[parent[a]].size() < sets[parent[b]].size()) {
                            swap(a, b);
                        }
                        for (int x : sets[parent[b]]) {
                            parent[x] = parent[a];
                            sets[parent[a]].push_back(x);
                        }
                        sets[parent[b]].clear();
                    }
                }
                bool ok = true;
                for (int i = 0; i < n; i++) {
                    if (parent[i] != parent[0]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    return ret;
                }
            }
        }
    }
};  // namespace random_generator

struct setup_random {
    setup_random() {
        random_generator::init();
    }
} setup_random_instance;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int> P(N);
    iota(P.begin(), P.end(), 1);

    map<int, vector<int>> mp;

    do {
        int xorsum = 0;
        for (int i = 0; i < N; i++) {
            xorsum ^= (A[i] + P[i]);
        }

        if (mp.find(xorsum) != mp.end()) {
            for (int i = 0; i < N; i++) {
                cout << mp[xorsum][i] << " ";
            }
            cout << endl;
            for (int i = 0; i < N; i++) {
                cout << P[i] << " ";
            }
            cout << endl;
            return 0;
        } else {
            mp[xorsum] = P;
        }
    } while (next_permutation(P.begin(), P.end()));

    cout << -1 << endl;
}

yukicoder

結果

テストケース

ソースコード