QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#742946 | #3136. The Spectrum | vwxyz# | WA | 1ms | 3872kb | C++23 | 3.0kb | 2024-11-13 17:43:04 | 2024-11-13 17:43:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1000;
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, X1.back() - 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
4 2 2 2 4 4 6
output:
1 0 2 4 6
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3872kb
input:
5 3 3 6 9 9 12 12 15 18 21
output:
1 0 3 12 15 21
result:
wrong answer 1st lines differ - expected: '2', found: '1'