QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#521521 | #4930. LCS of Permutations | skittles1412# | 0 | 2143ms | 6064kb | C++17 | 4.8kb | 2024-08-16 11:45:31 | 2024-08-16 11:45:31 |
Judging History
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%