Submission #3627547

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int N, S0[8192], T[8192];
vector<int> X, Y, F; vector<string> S;
string def;

void permute_sub(int *dest, int block, int aug, int width)
{
    string s = def, t = def;
    for (int ori = 0; ori < N; ori += block) {
        for (int i = aug; i + 2 * width <= block; i += 2 * width) {
            for (int j = ori + i; j < ori + i + width; ++j) {
                int k = j + width;
                //printf("%d %d %d(%d), %d(%d)\n", ori, i, j, dest[j], k, dest[k]);
                if (dest[j] > dest[k]) {
                    s[k] = 'y';
                    t[j] = 'y';
                    swap(dest[j], dest[k]);
                }
            }
        }
    }
    int last = X.size();
    X.push_back(last); Y.push_back(last); F.push_back(width); S.push_back(s);
    X.push_back(last + 1); Y.push_back(last); F.push_back(-width); S.push_back(t);
}

void permute(int* dest)
{
    bool indest[8192];
    fill(indest, indest + N, false);
    for (int i = 0; i < N; ++i) {
        if (dest[i] != -1) indest[dest[i]] = true;
    }
    vector<int> not_in_dest;
    for (int i = 0; i < N; ++i) {
        if (!indest[i]) not_in_dest.push_back(i);
    }
    for (int i = 0; i < N; ++i) {
        if (dest[i] == -1) {
            dest[i] = not_in_dest.back();
            not_in_dest.pop_back();
        }
    }
    //for (int i = 0; i < N; ++i) printf("%d ", dest[i]); puts("");
    // the i-th element goes to the dest[i]-th element
    for (int w = 2; w <= N; w *= 2) {
        permute_sub(dest, w, 0, w / 2);
        for (int w2 = w / 2; w2 >= 2; w2 >>= 1) {
            permute_sub(dest, w, w2 / 2, w2 / 2);
        }
    }
}

int cntS[8200], cntT[8200], base[8200];
bool reprS[8192]; int occurIdT[8192];

int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d", S0 + i);
    for (int i = 0; i < N; ++i) scanf("%d", T + i);

    for (int i = 0; i < N; ++i) reprS[i] = (cntS[S0[i]]++ == 0);
    for (int i = 0; i < N; ++i) occurIdT[i] = cntT[T[i]]++;

    for (int i = 1; i <= N; ++i) {
        if (cntT[i] > 0 && cntS[i] == 0) {
            puts("-1");
            return 0;
        }
    }

    for (int i = 0; i < N; ++i) def.push_back('x');

    int dest[8192]; int acc = 0;
    vector<pair<int, int>> afterPerm;
    fill(dest, dest + N, -1);
    for (int i = 0; i < N; ++i) {
        if (reprS[i] && cntT[S0[i]] > 0) {
            dest[i] = acc;
            base[S0[i]] = acc;
            for (int j = 0; j < cntT[S0[i]]; ++j) afterPerm.push_back({S0[i], j});
            acc += cntT[S0[i]];
        }
    }

    permute(dest);
    for (int w = 1; w < N; w <<= 1) {
        string s = def;
        for (int i = 0; i < N; ++i) {
            if (w <= afterPerm[i].second && afterPerm[i].second < 2 * w) s[i] = 'y';
        }
        int last = S.size();
        X.push_back(last); Y.push_back(last); F.push_back(w); S.push_back(s);
    }

    for (int i = 0; i < N; ++i) dest[base[T[i]] + occurIdT[i]] = i;
    permute(dest);

    printf("%d\n", (int)S.size());
    for (int i = 0; i < S.size(); ++i) {
        printf("%d %d %d %s\n", X[i], Y[i], F[i], S[i].c_str());
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:66:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < N; ++i) scanf("%d", S0 + i);
                                                    ^
./Main.cpp:67:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < N; ++i) scanf("%d", T + i);
                                                   ^

Judge Result