QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742837#3136. The Spectrumvwxyz#WA 0ms3552kbC++232.6kb2024-11-13 17:26:302024-11-13 17:26:32

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 17:26:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3552kb
  • [2024-11-13 17:26:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'