Submission #1958959

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

const int MAX_N = 100000;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N, M, D;

    gc(N);
    gc(M);
    gc(D);

    vector<int> src(N, 0);
    vector<int> dst(N, 0);

    for (int i = 0; i < N; i++)
        src[i] = dst[i] = i;

    for (int i = 0; i < M; i++)
    {
        int A;
        gc(A);

        swap(dst[A - 1], dst[A]);
    }

    int log2D = (int)log2(D);

    vector< vector<int> > dbl(log2D + 1, vector<int>());

    copy(dst.begin(), dst.end(), back_inserter(dbl[0]));

    for (int i = 1; i < log2D + 1; i++)
    {
        vector<int> tmp;

        copy(dst.begin(), dst.end(), back_inserter(tmp));

        for (int j = 0; j < N; j++)
            dst[j] = tmp[dst[j]];

        copy(dst.begin(), dst.end(), back_inserter(dbl[i]));
    }

    int i = 0;
    while (D)
    {
        // 最下位ビット取り出し
        if (D & 1)
            for (int j = 0; j < N; j++)
                src[j] = dbl[i][src[j]];

        // 1桁右シフト
        D >>= 1;

        i++;
    }

    vector<int> res(N, 0);
    for (int i = 0; i < N; i++)
    {
        res[src[i]] = i + 1;
    }

    for (int i = 0; i < N; i++) printf("%d\n", res[i]);
    return 0;
}

Submission Info

Judge Result