QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742946#3136. The Spectrumvwxyz#WA 1ms3872kbC++233.0kb2024-11-13 17:43:042024-11-13 17:43:10

Judging History

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

  • [2024-11-13 17:43:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3872kb
  • [2024-11-13 17:43:04]
  • 提交

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'