QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742982#3136. The Spectrumvwxyz#AC ✓3021ms216836kbC++232.9kb2024-11-13 17:49:072024-11-13 17:49:07

Judging History

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

  • [2024-11-13 17:49:07]
  • 评测
  • 测评结果:AC
  • 用时:3021ms
  • 内存:216836kb
  • [2024-11-13 17:49:07]
  • 提交

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, 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: 3636kb

input:

4
2 2 2 4 4 6

output:

1
0 2 4 6

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3644kb

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: 3544kb

input:

4
5 6 7 8 9 10

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3960kb

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: 0
Accepted
time: 2546ms
memory: 180892kb

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:

2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 51 52 55 56 57 58 59 61 62 63 64 65 66 67 68 69 70 71 72 73
0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 21 22 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ...

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 5ms
memory: 4200kb

input:

60
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 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...

output:

1
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 10ms
memory: 4696kb

input:

62
1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13...

output:

2
0 2 11 15 17 18 24 31 40 44 47 51 58 61 69 79 85 91 98 107 109 113 121 130 140 144 147 148 154 155 160 167 177 183 188 191 192 196 200 206 212 219 224 226 230 237 246 249 252 261 266 273 283 290 294 295 297 302 306 310 311 319
0 8 9 13 17 22 24 25 29 36 46 53 58 67 70 73 82 89 93 95 100 107 113 11...

result:

ok 3 lines

Test #8:

score: 0
Accepted
time: 18ms
memory: 5032kb

input:

62
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 12 12 12 12 12 13 13 13 1...

output:

2
0 1 7 8 15 16 17 25 26 32 34 36 39 48 53 61 62 67 75 82 90 92 100 108 109 110 116 117 118 119 124 130 133 137 147 157 167 173 178 182 183 192 201 211 213 217 226 235 242 244 251 260 264 269 277 285 293 295 297 299 306 311
0 5 12 14 16 18 26 34 42 47 51 60 67 69 76 85 94 98 100 110 119 128 129 133 ...

result:

ok 3 lines

Test #9:

score: 0
Accepted
time: 6ms
memory: 4404kb

input:

60
1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 5 5 5 5 5 6 6 6 7 7 7 7 7 8 8 9 9 9 9 9 9 9 9 9 10 10 10 11 11 11 12 12 13 13 13 13 13 14 14 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 20 20 20 20 20 21 21 21 21 21 21 21 21 22 22 22 23 23 23 23 23 23 ...

output:

2
0 2 18 31 50 58 78 96 109 118 138 140 145 161 162 164 168 169 187 196 198 203 219 239 258 275 276 291 302 307 323 341 359 378 387 401 411 420 429 439 444 445 465 474 483 486 499 502 520 536 553 560 562 574 577 583 587 603 614 627
0 13 24 40 44 50 53 65 67 74 91 107 125 128 141 144 153 162 182 183 ...

result:

ok 3 lines

Test #10:

score: 0
Accepted
time: 6ms
memory: 4480kb

input:

60
1 1 1 2 2 2 2 3 3 3 3 4 4 6 6 6 7 7 7 8 8 8 8 8 8 9 9 9 9 9 9 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 13 13 13 13 13 14 14 15 15 15 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 20 20 20 20 20 20 21 21 21 21 22 22 22 23 23 23 23 23 23 2...

output:

2
0 10 18 20 39 45 52 68 81 99 111 126 127 142 150 153 162 163 178 197 205 208 219 231 242 251 262 271 287 294 312 328 329 338 345 357 368 379 382 395 401 403 405 414 431 442 459 463 469 489 498 501 509 526 542 558 560 576 584 604
0 20 28 44 46 62 78 95 103 106 115 135 141 145 162 173 190 199 201 20...

result:

ok 3 lines

Test #11:

score: 0
Accepted
time: 6ms
memory: 4616kb

input:

60
1 2 2 2 3 3 3 4 4 4 5 6 6 6 7 7 7 8 8 8 9 9 9 9 10 10 11 11 11 11 11 12 12 12 12 12 12 12 12 13 13 13 14 15 15 15 15 15 16 16 16 17 18 18 18 19 19 19 19 19 19 20 20 20 20 21 21 21 21 21 21 22 22 22 22 22 23 23 24 25 25 25 25 25 25 25 25 25 26 26 26 26 26 27 27 27 27 27 27 28 28 28 28 29 29 29 29 ...

output:

2
0 2 29 33 38 41 49 69 80 95 125 152 181 207 229 236 242 245 261 264 281 306 313 328 353 364 365 371 390 392 402 413 415 427 449 453 474 492 500 504 519 546 570 590 599 605 630 651 663 681 691 700 712 727 749 768 779 800 813 825
0 12 25 46 57 76 98 113 125 134 144 162 174 195 220 226 235 255 279 30...

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 3021ms
memory: 216836kb

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 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 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...

output:

2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 20 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 52 54 56 57 58 61 62 63 64 65 66 67 68 69 70 71 72 73
0 1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 19 21 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ...

result:

ok 3 lines

Test #13:

score: 0
Accepted
time: 2786ms
memory: 200164kb

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 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 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 3...

output:

2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 18 19 20 22 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 50 52 56 57 59 61 62 63 64 65 66 67 68 69 70 71 72 73
0 1 2 3 4 5 6 7 8 9 10 11 12 14 16 17 21 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 51 ...

result:

ok 3 lines