QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#742981 | #3136. The Spectrum | vwxyz# | RE | 1ms | 3804kb | C++23 | 2.9kb | 2024-11-13 17:48:42 | 2024-11-13 17:48:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 30;
int N;
vector<int> A;
vector<int> cnt(M, 0);
unordered_map<string, set<vector<int>>> memo;
int R;
string get_key(const vector<int>& X0, const vector<int>& X1, const vector<int>& cnt) {
stringstream ss;
for (int x : X0) ss << x << ",";
ss << "|";
for (int x : X1) ss << x << ",";
ss << "|";
for (int x : cnt) ss << x << ",";
return ss.str();
}
set<vector<int>> solve(vector<int> X0, vector<int> X1, vector<int> cnt) {
string key = get_key(X0, X1, cnt);
if (memo.count(key)) return memo[key];
if (*max_element(cnt.begin(), cnt.end()) == 0) {
vector<int> result(X0);
result.insert(result.end(), X1.rbegin(), X1.rend());
return memo[key] = {result};
}
set<vector<int>> retu;
if (X0.back() < X1.back()) {
for (int d = M - 1; d >= 0; --d) {
if (cnt[d]) {
for (int y : {d, R - d}) {
if (X0.back() < y && y < X1.back() && max(R - d, d) == d) {
vector<int> cnt_ = cnt;
bool ok = true;
for (int x : X0) {
cnt_[abs(x - y)]--;
if (cnt_[abs(x - y)] < 0) ok = false;
}
for (int x : X1) {
cnt_[abs(x - y)]--;
if (cnt_[abs(x - y)] < 0) ok = false;
}
if (ok) {
if (y == d) {
vector<int> X1_=X1;
X1_.push_back(y);
auto sub_ans = solve(X0, X1_, cnt_);
retu.insert(sub_ans.begin(), sub_ans.end());
} else {
vector<int> X0_=X0;
X0_.push_back(y);
auto sub_ans = solve(X0_, X1, cnt_);
retu.insert(sub_ans.begin(), sub_ans.end());
}
}
}
}
break;
}
}
}
return memo[key] = retu;
}
int main() {
cin >> N;
A.resize(N*(N-1)/2);
for (int i = 0; i < N*(N-1)/2; ++i) {
cin >> A[i];
cnt[A[i]]++;
}
int L = 0;
R = *max_element(A.begin(), A.end());
cnt[R - L]--;
auto ans_lst = solve({L}, {R}, cnt);
vector<vector<int>> ans_vec(ans_lst.begin(), ans_lst.end());
sort(ans_vec.begin(), ans_vec.end());
cout << ans_vec.size() << endl;
for (const auto& ans : ans_vec) {
for (size_t i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
input:
4 2 2 2 4 4 6
output:
1 0 2 4 6
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 3 3 6 9 9 12 12 15 18 21
output:
2 0 3 12 15 21 0 6 9 18 21
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4 5 6 7 8 9 10
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
9 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 5 6 6 7 7 8 8 8 9 9 10 10 11 11 12 12 12 13 14 15
output:
4 0 1 3 4 5 7 12 13 15 0 1 3 8 9 11 12 13 15 0 2 3 4 6 7 12 14 15 0 2 3 8 10 11 12 14 15
result:
ok 5 lines
Test #5:
score: -100
Runtime Error
input:
62 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
output:
0