QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521556#4930. LCS of Permutationsskittles1412#Compile Error//C++173.9kb2024-08-16 12:08:002024-08-16 12:08:01

Judging History

你现在查看的是最新测评结果

  • [2024-08-16 12:08:01]
  • 评测
  • [2024-08-16 12:08:00]
  • 提交

answer

#include "template.hpp"

int lcs(const vector<int>& arra, const vector<int>& arrb) {
    int n = sz(arra), m = sz(arrb);

    vector dp(n + 1, vector(m + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            if (arra[i] == arrb[j]) {
                dp[i][j] = max(dp[i][j], 1 + dp[i + 1][j + 1]);
            }
        }
    }

    return dp[0][0];
}

struct Solver {
    int n, m;
    vector<vector<int>> perms, dist;

    Solver() {}
    Solver(int n) : n(n) {
        {
            auto carr = iota(n, 0);
            do {
                perms.push_back(carr);
            } while (next_permutation(begin(carr), end(carr)));
        }

        m = sz(perms);
        dist = vector(m, vector(m, int(0)));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                dist[i][j] = lcs(perms[i], perms[j]);
            }
        }
    }

    array<vector<int>, 3> solve(int a, int b, int c) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (dist[0][i] == a && dist[0][j] == b && dist[i][j] == c) {
                    return {perms[0], perms[i], perms[j]};
                }
            }
        }
        return {};
    }
};

vector<Solver> solvers = []() {
    vector<Solver> ans(7);
    for (int i = 1; i <= 6; i++) {
        ans[i] = Solver(i);
    }
    return ans;
}();

void solve() {
    int n, ka, kb, kc, t_out;
    cin >> n >> ka >> kb >> kc >> t_out;

    auto print_line = [&](const vector<int>& arr) -> void {
        for (int i = 0; i < n; i++) {
            cout << arr[i] + 1 << " \n"[i == n - 1];
        }
    };

    if (ka == 1 && kb == 1 && kc == n && t_out) {
        cout << "YES" << endl;
        print_line(reversed(iota(n, 0)));
        print_line(iota(n, 0));
        print_line(iota(n, 0));
        return;
    }

    if (kc == n && t_out) {
        if (ka != kb) {
            cout << "NO" << endl;
            return;
        }
        cout << "YES" << endl;

        auto v1 = reversed(iota(n, 0));
        reverse(begin(v1), begin(v1) + ka);
        print_line(v1);
        print_line(iota(n, 0));
        print_line(iota(n, 0));
        return;
    }

    if (ka == 1 && t_out) {
        if (long(kb) * kc < n || kb + kc - 1 > n) {
            auto ans = solvers[n].solve(ka, kb, kc);
            assert(!sz(ans[0]));
            cout << "NO" << endl;
            return;
        }

        auto v1 = reversed(iota(n, 0));
        dbg(v1);
        int clen = 0, ci = 0;
        while (true) {
            assert(ci < n);
            clen++;
            int cr = min(n, ci + kb);
            if (clen + n - cr <= kc) {
                cr = clen + n - kc;
                reverse(begin(v1) + ci, begin(v1) + cr);
                break;
            }
            reverse(begin(v1) + ci, begin(v1) + cr);
            ci = cr;
        }

        print_line(iota(n, 0));
        print_line(reversed(iota(n, 0)));
        print_line(v1);
        assert(lcs(iota(n, 0), v1) == kb);
        assert(lcs(reversed(iota(n, 0)), v1) == kc);
        return;
    }

    if (n <= 6) {
        if (ka == 1 && (long(kb) * kc < n || kb + kc - 1 > n)) {
            auto ans = solvers[n].solve(ka, kb, kc);
            assert(!sz(ans[0]));
            cout << "NO" << endl;
            return;
        }
        auto ans = solvers[n].solve(ka, kb, kc);
        if (!sz(ans[0])) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
            if (t_out) {
                for (auto& a : ans) {
                    print_line(a);
                }
            }
        }
        return;
    }
}

int main() {
    init_io();
    int tcs;
    cin >> tcs;
    while (tcs--) {
        solve();
    }
}

Details

answer.code:1:10: fatal error: template.hpp: No such file or directory
    1 | #include "template.hpp"
      |          ^~~~~~~~~~~~~~
compilation terminated.