Submission #4993240


Source Code Expand

Copy
#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

Submission Time
Task D - A Sequence of Permutations
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1780 Byte
Status
Exec Time 77 ms
Memory 3824 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt
All 1000 / 1000 sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt 2 ms 384 KB
in02.txt 6 ms 512 KB
in03.txt 7 ms 552 KB
in04.txt 6 ms 568 KB
in05.txt 4 ms 384 KB
in06.txt 2 ms 256 KB
in07.txt 2 ms 384 KB
in08.txt 4 ms 384 KB
in09.txt 6 ms 512 KB
in10.txt 7 ms 540 KB
in11.txt 66 ms 3484 KB
in12.txt 71 ms 3716 KB
in13.txt 68 ms 3600 KB
in14.txt 70 ms 3712 KB
in15.txt 67 ms 3528 KB
in16.txt 67 ms 3516 KB
in17.txt 66 ms 3456 KB
in18.txt 71 ms 3608 KB
in19.txt 63 ms 3332 KB
in20.txt 76 ms 3712 KB
in21.txt 74 ms 3712 KB
in22.txt 77 ms 3712 KB
in23.txt 73 ms 3608 KB
in24.txt 67 ms 3332 KB
in25.txt 71 ms 3600 KB
in26.txt 69 ms 3484 KB
in27.txt 71 ms 3620 KB
in28.txt 70 ms 3528 KB
in29.txt 68 ms 3456 KB
in30.txt 65 ms 3296 KB
in31.txt 2 ms 256 KB
in32.txt 2 ms 256 KB
in33.txt 2 ms 256 KB
in34.txt 2 ms 256 KB
in35.txt 2 ms 256 KB
in36.txt 2 ms 256 KB
in37.txt 76 ms 3824 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB
sample03.txt 1 ms 256 KB