QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#742982 | #3136. The Spectrum | vwxyz# | AC ✓ | 3021ms | 216836kb | C++23 | 2.9kb | 2024-11-13 17:49:07 | 2024-11-13 17:49:07 |
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, 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;
}
详细
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