QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#742837 | #3136. The Spectrum | vwxyz# | WA | 0ms | 3552kb | C++23 | 2.6kb | 2024-11-13 17:26:30 | 2024-11-13 17:26:32 |
Judging History
answer
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;
const int M = 25;
// キー型(vector<int>, (int, int, int))の比較関数
struct KeyCompare {
bool operator()(const pair<vector<int>, tuple<int, int, int>>& a,
const pair<vector<int>, tuple<int, int, int>>& b) const {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
}
};
// メモ化されたsolve関数の定義
map<vector<vector<int>>, set<vector<int>>> memo;
set<vector<int>> solve(vector<int> X, vector<int> cnt, int l, int r) {
vector<vector<int>> key = {X,cnt,{l,r}};
if (memo.find(key) != memo.end()) return memo[key];
set<vector<int>> retu;
if (*max_element(cnt.begin(), cnt.end()) == 0) {
retu.insert(X);
} else if (l < r) {
for (int d = M - 1; d >= 0; --d) {
if (cnt[d]) {
for (int y : {d, r - d}) {
if (l < y && y < r && max(r - d, d) == d) {
vector<int> cnt_ = cnt;
bool ok = true;
for (int x : X) {
cnt_[abs(x - y)]--;
if (cnt_[abs(x - y)] < 0) {
ok = false;
break;
}
}
if (ok) {
vector<int> X_next = X;
X_next.push_back(y);
sort(X_next.begin(), X_next.end());
retu.merge(solve(X_next, cnt_, y, r));
retu.merge(solve(X_next, cnt_, l, y));
}
}
}
break;
}
}
}
return memo[key] = retu;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N*(N-1)/2);
vector<int> cnt(M, 0);
int R = 0;
for (int i = 0; i < N*(N-1)/2; ++i) {
cin >> A[i];
cnt[A[i]]++;
R = max(R, A[i]);
}
int L = 0;
cnt[R - L]--;
set<vector<int>> ans_lst = solve({L, R}, cnt, L, R);
cout << ans_lst.size() << '\n';
for (const auto& ans : ans_lst) {
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
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: 0ms
memory: 3552kb
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'