QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521516#4930. LCS of Permutationsskittles1412#8 2178ms5828kbC++174.6kb2024-08-16 11:41:092024-08-16 11:41:11

Judging History

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

  • [2024-08-16 11:41:11]
  • 评测
  • 测评结果:8
  • 用时:2178ms
  • 内存:5828kb
  • [2024-08-16 11:41:09]
  • 提交

answer

// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using u64 = uint64_t;
using ll = long long;
using ld = long double;

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
vector<T> iota(int n, const T& init) {
    vector<T> arr(n);

    iota(begin(arr), end(arr), init);

    return arr;
}

template <typename T>
vector<vector<T>> transposed(const vector<vector<T>>& arr) {
    int n = sz(arr), m = sz(arr[0]);

    vector ans(m, vector<T>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans[j][i] = arr[i][j];
        }
    }

    return ans;
}

template <typename T>
bool on(const T& mask, int bit) {
    return (mask >> bit) & 1;
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T, size_t N>
ostream& operator<<(ostream& out, const array<T, N>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template <typename A, typename T>
int lbs(const A& arr, const T& x) {
    return int(lower_bound(begin(arr), end(arr), x) - begin(arr));
}

inline vector<bool>::reference& operator&=(vector<bool>::reference&& a, bool b) {
    return a = a & b;
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

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;

    if (n <= 6) {
        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) {
                    for (int i = 0; i < n; i++) {
                        cout << a[i] + 1 << " \n"[i == n - 1];
                    }
                }
            }
        }
    }
}

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

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 112ms
memory: 5772kb

input:

632
512 1 1 512 1
201 1 1 201 1
155 1 1 155 1
129 1 1 129 1
345 1 1 345 1
454 1 1 454 1
614 1 1 614 1
11 1 1 11 1
492 1 1 492 1
357 1 1 357 1
300 1 1 300 1
295 1 1 295 1
607 1 1 607 1
442 1 1 442 1
14 1 1 14 1
79 1 1 79 1
584 1 1 584 1
431 1 1 431 1
343 1 1 343 1
64 1 1 64 1
548 1 1 548 1
101 1 1 10...

output:

YES
1 2 3
3 2 1
3 2 1
YES
1 2 3 4 5 6
6 5 4 3 2 1
6 5 4 3 2 1
YES
1 2 3 4
4 3 2 1
4 3 2 1
YES
1
1
1
YES
1 2
2 1
2 1
YES
1 2 3 4 5
5 4 3 2 1
5 4 3 2 1

result:

wrong output format Expected integer, but "YES" found (test case 1)

Subtask #2:

score: 8
Accepted

Test #9:

score: 8
Accepted
time: 2178ms
memory: 5828kb

input:

40011
1 1 1 1 1
2 1 1 1 1
2 1 1 2 1
2 1 2 2 1
2 2 2 2 1
3 1 1 1 1
3 1 1 2 1
3 1 1 3 1
3 1 2 2 1
3 1 2 3 1
3 1 3 3 1
3 2 2 2 1
3 2 2 3 1
3 2 3 3 1
3 3 3 3 1
4 1 1 1 1
4 1 1 2 1
4 1 1 3 1
4 1 1 4 1
4 1 2 2 1
4 1 2 3 1
4 1 2 4 1
4 1 3 3 1
4 1 3 4 1
4 1 4 4 1
4 2 2 2 1
4 2 2 3 1
4 2 2 4 1
4 2 3 3 1
4 2 ...

output:

YES
1
1
1
NO
YES
1 2
2 1
2 1
NO
YES
1 2
1 2
1 2
NO
NO
YES
1 2 3
3 2 1
3 2 1
YES
1 2 3
3 2 1
1 3 2
NO
NO
YES
1 2 3
1 3 2
2 1 3
YES
1 2 3
1 3 2
1 3 2
NO
YES
1 2 3
1 2 3
1 2 3
NO
NO
NO
YES
1 2 3 4
4 3 2 1
4 3 2 1
YES
1 2 3 4
4 3 2 1
2 1 4 3
YES
1 2 3 4
4 3 2 1
1 4 3 2
NO
NO
NO
NO
YES
1 2 3 4
1 4 3 2
2 ...

result:

ok Correct (40011 test cases)

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #58:

score: 0
Wrong Answer
time: 122ms
memory: 5696kb

input:

11753
20 10 12 19 0
21 3 4 18 0
21 5 12 14 0
7 1 1 3 0
16 9 10 13 0
13 3 4 9 0
21 11 13 14 0
16 15 16 16 0
20 10 10 13 0
19 3 9 13 0
18 1 17 18 0
15 2 4 4 0
14 2 4 5 0
19 3 9 16 0
16 10 12 15 0
18 2 7 17 0
18 1 1 12 0
14 1 1 1 0
9 1 2 5 0
17 8 15 15 0
18 2 2 14 0
19 9 14 17 0
20 2 10 16 0
20 8 9 17 ...

output:

YES
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES...

result:

wrong answer Wrong answer (test case 1)

Subtask #6:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #3:

0%