QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#521516 | #4930. LCS of Permutations | skittles1412# | 8 | 2178ms | 5828kb | C++17 | 4.6kb | 2024-08-16 11:41:09 | 2024-08-16 11:41:11 |
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;
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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%