QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521521#4930. LCS of Permutationsskittles1412#0 2143ms6064kbC++174.8kb2024-08-16 11:45:312024-08-16 11:45:31

Judging History

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

  • [2024-08-16 11:45:31]
  • 评测
  • 测评结果:0
  • 用时:2143ms
  • 内存:6064kb
  • [2024-08-16 11:45:31]
  • 提交

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;

    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) {
        print_line(reversed(iota(n, 0)));
        print_line(iota(n, 0));
        print_line(iota(n, 0));
        return;
    }

    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) {
                    print_line(a);
                }
            }
        }
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 134ms
memory: 5804kb

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:

512 511 510 509 508 507 506 505 504 503 502 501 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 ...

result:

wrong answer Token parameter [name=yes/no] equals to "512", doesn't correspond to pattern "[yY][eE][sS]|[nN][oO]" (test case 1)

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 2143ms
memory: 5788kb

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:

1
1
1
NO
2 1
1 2
1 2
NO
YES
1 2
1 2
1 2
NO
NO
3 2 1
1 2 3
1 2 3
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
4 3 2 1
1 2 3 4
1 2 3 4
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 4 1 3
YES
1 2 3 ...

result:

wrong answer Token parameter [name=yes/no] equals to "1", doesn't correspond to pattern "[yY][eE][sS]|[nN][oO]" (test case 1)

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: 6064kb

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:

0%