Submission #4993240

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
vector<int> invert(vector<int> const & p) {
    vector<int> q(p.size());
    REP (i, p.size()) {
        q[p[i]] = i;
    }
    return q;
}
vector<int> multiply(vector<int> const & p, vector<int> const & q) {
    assert (p.size() == q.size());
    vector<int> r(p.size());
    REP (i, p.size()) {
        r[i] = p[q[i]];
    }
    return r;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

vector<int> invert(vector<int> const & p) {
    vector<int> q(p.size());
    REP (i, p.size()) {
        q[p[i]] = i;
    }
    return q;
}

vector<int> multiply(vector<int> const & p, vector<int> const & q) {
    assert (p.size() == q.size());
    vector<int> r(p.size());
    REP (i, p.size()) {
        r[i] = p[q[i]];
    }
    return r;
}

vector<int> power(vector<int> p, ll k) {
    vector<int> q(p.size());
    iota(ALL(q), 0);
    for (ll i = 1; i <= k; i <<= 1) {
        if (k & i) q = multiply(q, p);
        p = multiply(p, p);
    }
    return q;
}

vector<int> solve(int n, ll k, vector<int> const & p, vector<int> const & q) {
    int kq = (k - 1) / 6;
    int kr = (k - 1) % 6;
    vector<int> a = power(multiply(q, multiply(invert(p), multiply(invert(q), p))), kq);
    switch (kr) {
        case 3:
            a = multiply(a, q);
            break;
        case 4:
        case 5:
            a = multiply(a, multiply(q, invert(p)));
            break;
    }
    vector<int> b =
        kr == 0 ? p :
        kr == 1 ? q :
        kr == 2 ? multiply(q, invert(p)) :
        kr == 3 ? invert(p) :
        kr == 4 ? invert(q) :
                  multiply(invert(q), p);
    return multiply(a, multiply(b, invert(a)));
}

int main() {
    // input
    int n; ll k; cin >> n >> k;
    vector<int> p(n);
    REP (i, n) {
        cin >> p[i];
        -- p[i];
    }
    vector<int> q(n);
    REP (i, n) {
        cin >> q[i];
        -- q[i];
    }

    // solve
    vector<int> r = solve(n, k, p, q);

    // output
    REP (i, n) {
        cout << r[i] + 1 << ' ';
    }
    cout << endl;
    return 0;
}

Submission Info

Judge Result