QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #783269 | #124. Library | makrav | 100 ✓ | 34ms | 4344kb | C++20 | 4.1kb | 2024-11-26 05:48:08 | 2024-11-26 05:48:10 |
Judging History
answer
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rnd1(time(NULL));
template<typename T>
void shuf(vector<T>& a) {
for (int i = 1; i < sz(a); i++) swap(a[i], a[rnd1() % (i + 1)]);
}
void Solve(int N) {
vector<int> Q(N);
int n = N;
vector<vector<int>> g_ans(n);
vector<int> answ, used(n, 0);
auto dfs_ans = [&](int v, auto&&self) -> void {
used[v] = 1;
answ.pb(v + 1);
for (int u : g_ans[v]) {
if (!used[u]) self(u, self);
}
};
if (N <= 200) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Q[i] = Q[j] = 1;
if (Query(Q) == 1) {
g_ans[i].pb(j);
g_ans[j].pb(i);
}
Q[i] = Q[j] = 0;
}
}
for (int i = 0; i < n; i++) {
if (g_ans[i].size() <= 1) {
dfs_ans(i, dfs_ans);
Answer(answ);
break;
}
}
return;
}
vector<int> ord(n, 0);
iota(all(ord), 0);
int cur = 0;
const int K = 6;
for (int i = 0; i < K; i++) {
shuf(ord);
for (int j = 0; j < n; j++) {
if (Q[ord[j]]) continue;
Q[ord[j]] = 1;
cur++;
if (Query(Q) == cur) {
//cout << "yes " << ord[j] << ' ' << cur << '\n';
continue;
}
Q[ord[j]] = 0;
cur--;
}
//cout << cur << '\n';
}
//cout << cur << '\n';
vector<int> lol, badg;
for (int i = 0; i < n; i++) {
if (Q[i]) {
Q[i] = 0;
lol.pb(i);
} else {
badg.pb(i);
}
}
vector<int> AP(sz(badg) + 1);
for (int i = 0;i<sz(badg); i++){
Q[badg[i]] = 1;
AP[i+1]=Query(Q);
}
vector<int> AP_rev(sz(badg) + 1);
for (int &el:Q)el=0;
reverse(all(badg));
for (int i = 0;i<sz(badg); i++){
Q[badg[i]] = 1;
AP_rev[i+1]=Query(Q);
}
for (int &el:Q)el=0;
reverse(all(badg));
for (int el : lol) {
Q[el] = 1;
int PP = -1;
{
int L = 0, R = sz(badg) + 1;
while (R - L > 1) {
int M = (L + R) / 2;
for (int i = 0; i < M; i++) Q[badg[i]] = 1;
if (Query(Q) == AP[M] + 1) L = M;
else R = M;
for (int i = 0; i < M; i++) Q[badg[i]] = 0;
}
if (R!=sz(badg)+1){
//cout<<el<<' '<<badg[R-1]<<'\n';
PP=badg[R-1];
g_ans[el].pb(badg[R - 1]);
g_ans[badg[R - 1]].pb(el);
}
}
reverse(all(badg));
{
int L = 0, R = sz(badg) + 1;
while (R - L > 1) {
int M = (L + R) / 2;
for (int i = 0; i < M; i++) Q[badg[i]] = 1;
if (Query(Q) == AP_rev[M] + 1) L = M;
else R = M;
for (int i = 0; i < M; i++) Q[badg[i]] = 0;
}
if (R!=sz(badg)+1&&PP!=badg[R-1]){
//cout<<el<<' '<<badg[R-1]<<'\n';
g_ans[el].pb(badg[R - 1]);
g_ans[badg[R - 1]].pb(el);
}
}
reverse(all(badg));
Q[el] = 0;
}
vector<int> badv;
for (int i = 0; i < n; i++) {
if (g_ans[i].size() <= 1) {
//cout<<i+1<<' ';
badv.pb(i);
}
}
//cout<<"\n";
int C = 0;
vector<int> fh, sh;
for (int el : badv) {
Q[el] = 1;
C++;
if (Query(Q) == C) {
fh.pb(el);
continue;
}
sh.pb(el);
C--;
Q[el] = 0;
}
lol = fh;
badg = sh;
//cout << sz(lol) << ' ' << sz(badg) << '\n';
for (int&el : Q) el = 0;
for (int el : lol) {
Q[el] = 1;
int L = 0, R = sz(badg) + 1;
while (R - L > 1) {
int M = (L + R) / 2;
for (int i = 0; i < M; i++) Q[badg[i]] = 1;
if (Query(Q) == M + 1) L = M;
else R = M;
for (int i = 0; i < M; i++) Q[badg[i]] = 0;
}
if (R < sz(badg) + 1) {
g_ans[el].pb(badg[R - 1]);
g_ans[badg[R - 1]].pb(el);
}
//cout << badg[R - 1] << '\n';
// reverse(all(badg));
// L = 0; R = sz(badg);
// while (R - L > 1) {
// int M = (L + R) / 2;
// for (int i = 0; i < M; i++) Q[badg[i]] = 1;
// if (Query(Q) == M + 1) L = M;
// else R = M;
// for (int i = 0; i < M; i++) Q[badg[i]] = 0;
// }
// g_ans[el].pb(badg[R - 1]);
// g_ans[badg[R - 1]].pb(el);
Q[el] = 0;
}
for (int i = 0; i < n; i++) {
if (g_ans[i].size() <= 1) {
dfs_ans(i, dfs_ans);
Answer(answ);
break;
}
}
return;
}
详细
Subtask #1:
score: 19
Accepted
Test #1:
score: 19
Accepted
time: 8ms
memory: 3848kb
input:
192 17 6 145 10 132 34 129 8 137 157 65 54 138 85 60 190 52 75 179 23 167 41 117 186 165 26 111 73 49 92 3 81 96 11 152 45 56 33 182 15 130 166 105 19 158 159 156 149 169 153 106 134 114 148 124 80 28 68 184 62 104 67 150 128 175 116 144 183 189 151 173 39 108 71 79 5 47 99 162 163 177 69 20 136 82 ...
output:
Accepted : 18336
result:
ok
Test #2:
score: 19
Accepted
time: 8ms
memory: 3888kb
input:
191 69 178 96 53 32 141 87 158 154 29 44 164 113 17 81 75 147 166 124 50 184 142 48 98 168 66 60 130 151 55 30 133 19 175 177 138 25 149 110 12 119 108 173 71 136 172 150 39 117 13 144 40 91 70 102 121 186 191 24 157 185 2 86 163 131 99 135 65 22 174 139 115 106 23 125 20 34 82 90 77 182 132 85 9 18...
output:
Accepted : 18145
result:
ok
Test #3:
score: 19
Accepted
time: 9ms
memory: 3852kb
input:
200 142 34 69 26 136 143 176 140 115 181 3 41 79 178 10 153 121 42 118 177 65 120 148 165 103 55 188 23 112 196 144 9 168 73 117 149 89 157 108 123 93 47 70 48 91 107 56 146 180 38 193 13 85 164 129 101 80 92 109 124 77 156 81 175 63 49 189 116 102 169 52 200 161 199 170 64 174 198 135 183 151 90 35...
output:
Accepted : 19900
result:
ok
Test #4:
score: 19
Accepted
time: 9ms
memory: 4192kb
input:
200 91 162 140 77 52 56 37 65 50 147 106 57 193 121 103 47 83 119 185 126 76 154 166 163 123 63 129 6 48 114 49 178 45 136 132 53 177 80 171 197 68 122 19 130 26 192 150 149 108 196 72 1 188 172 66 191 93 3 142 18 170 12 42 15 187 25 75 20 28 131 59 101 23 115 181 10 51 70 153 40 39 195 46 127 120 2...
output:
Accepted : 19900
result:
ok
Test #5:
score: 19
Accepted
time: 9ms
memory: 4196kb
input:
200 6 107 47 4 119 28 33 189 181 129 138 27 93 136 43 63 124 112 162 75 81 30 149 150 131 186 17 7 139 178 133 123 32 46 160 199 184 67 193 90 130 164 98 92 156 72 104 77 110 65 135 29 68 159 3 195 196 180 49 102 190 66 37 185 147 99 200 1 176 57 152 70 191 167 76 11 58 144 161 169 126 84 122 105 9 ...
output:
Accepted : 19900
result:
ok
Test #6:
score: 19
Accepted
time: 9ms
memory: 3900kb
input:
200 119 131 73 170 89 113 103 5 72 178 91 85 64 12 166 138 175 82 136 147 96 75 127 11 61 78 184 111 80 172 181 139 81 191 199 180 124 20 135 13 68 44 130 176 120 36 48 162 188 29 54 41 98 45 58 158 126 183 182 84 66 51 117 55 28 42 187 50 69 122 114 70 23 194 174 186 167 100 155 128 27 107 3 74 47 ...
output:
Accepted : 19900
result:
ok
Test #7:
score: 19
Accepted
time: 9ms
memory: 3904kb
input:
200 62 181 22 131 103 47 11 87 197 61 63 17 116 199 172 117 95 193 161 147 101 80 156 187 34 24 132 75 29 160 71 112 138 174 102 65 139 31 52 55 60 82 42 91 77 200 48 93 108 106 128 150 6 115 144 45 163 149 107 119 177 173 3 167 74 86 114 13 189 100 179 176 169 194 162 18 68 14 25 148 69 94 164 57 1...
output:
Accepted : 19900
result:
ok
Test #8:
score: 19
Accepted
time: 2ms
memory: 3904kb
input:
193 67 133 62 43 184 187 123 9 103 34 102 143 119 42 12 150 25 70 45 35 110 113 76 177 139 149 118 130 168 186 64 58 82 39 141 178 53 138 182 131 56 52 140 60 188 72 111 114 162 112 95 109 10 3 84 108 47 15 134 81 122 74 156 1 100 50 5 27 171 175 94 166 193 160 46 18 116 38 172 121 181 144 98 127 15...
output:
Accepted : 18528
result:
ok
Test #9:
score: 19
Accepted
time: 9ms
memory: 3828kb
input:
199 166 45 85 139 135 30 65 2 36 159 143 5 76 16 146 82 156 20 154 31 195 193 35 192 165 48 41 118 56 109 173 70 91 132 68 1 131 121 134 100 119 97 79 46 164 12 43 15 64 71 176 190 188 158 27 88 124 7 177 87 187 25 75 98 21 114 194 24 130 145 23 198 66 110 175 152 34 115 19 53 58 162 149 57 49 163 5...
output:
Accepted : 19701
result:
ok
Test #10:
score: 19
Accepted
time: 3ms
memory: 3900kb
input:
129 34 75 74 78 64 110 38 6 35 100 76 126 87 102 90 71 52 127 108 7 104 37 97 72 25 116 66 8 92 91 26 99 4 12 18 48 56 81 69 3 105 70 20 51 44 83 62 21 123 19 86 28 50 84 32 77 46 80 24 115 41 89 27 33 1 9 93 120 40 107 49 39 98 2 119 118 122 14 55 16 113 109 124 54 73 47 85 15 101 42 45 57 128 65 6...
output:
Accepted : 8256
result:
ok
Test #11:
score: 19
Accepted
time: 0ms
memory: 4192kb
input:
1 1
output:
Accepted : 0
result:
ok
Test #12:
score: 19
Accepted
time: 0ms
memory: 3948kb
input:
2 2 1
output:
Accepted : 1
result:
ok
Test #13:
score: 19
Accepted
time: 0ms
memory: 3964kb
input:
3 2 1 3
output:
Accepted : 3
result:
ok
Test #14:
score: 19
Accepted
time: 0ms
memory: 3892kb
input:
4 4 2 3 1
output:
Accepted : 6
result:
ok
Test #15:
score: 19
Accepted
time: 0ms
memory: 3968kb
input:
15 6 14 3 4 8 2 7 5 11 13 10 15 12 9 1
output:
Accepted : 105
result:
ok
Test #16:
score: 19
Accepted
time: 0ms
memory: 3832kb
input:
27 22 16 19 13 4 26 1 15 17 24 6 25 12 27 2 7 10 21 20 8 11 23 3 5 14 18 9
output:
Accepted : 351
result:
ok
Subtask #2:
score: 81
Accepted
Test #17:
score: 81
Accepted
time: 34ms
memory: 4036kb
input:
1000 972 265 212 27 724 465 50 304 37 134 246 257 177 482 90 974 616 221 151 912 946 366 590 277 187 976 394 765 643 740 385 665 749 585 923 92 920 994 48 405 978 893 477 381 788 992 825 680 785 297 679 116 836 31 333 714 828 922 492 890 919 237 188 677 557 522 867 368 19 690 29 632 832 17 107 485 3...
output:
Accepted : 14157
result:
ok
Test #18:
score: 81
Accepted
time: 33ms
memory: 4332kb
input:
989 307 977 634 651 311 322 806 970 412 721 516 193 497 205 58 925 736 478 441 377 423 980 351 661 406 594 837 929 308 220 116 665 815 802 931 85 581 877 372 236 964 739 650 593 280 795 918 273 733 182 813 266 924 723 692 61 710 872 94 573 613 212 286 978 167 622 128 885 898 487 725 923 705 915 483 ...
output:
Accepted : 14040
result:
ok
Test #19:
score: 81
Accepted
time: 34ms
memory: 4036kb
input:
1000 832 936 416 950 25 253 637 669 760 852 468 731 524 976 999 861 304 293 537 207 565 375 47 3 748 400 679 103 302 466 110 794 467 601 991 137 969 894 83 790 1 239 858 680 68 371 264 323 104 123 69 57 521 427 802 683 709 641 134 824 547 377 255 980 118 638 846 645 883 841 44 795 247 109 652 543 30...
output:
Accepted : 14145
result:
ok
Test #20:
score: 81
Accepted
time: 30ms
memory: 4296kb
input:
942 797 548 479 718 546 775 620 832 908 198 9 606 862 633 392 700 337 32 694 31 277 590 92 507 278 348 50 896 148 926 681 328 568 290 79 228 722 498 738 12 110 859 416 383 665 203 927 678 137 354 182 304 180 221 56 868 531 154 843 554 481 516 863 504 258 60 250 222 361 151 33 374 378 612 166 685 263...
output:
Accepted : 13274
result:
ok
Test #21:
score: 81
Accepted
time: 26ms
memory: 4316kb
input:
893 302 891 160 353 426 852 54 680 269 569 807 516 176 564 770 193 799 445 844 520 364 429 382 724 877 650 398 416 157 161 467 540 73 624 120 544 275 36 497 838 833 71 365 460 458 768 271 565 34 378 585 811 180 660 587 15 783 631 493 477 831 367 482 824 436 791 803 533 244 355 163 106 752 695 615 33...
output:
Accepted : 12398
result:
ok
Test #22:
score: 81
Accepted
time: 33ms
memory: 4040kb
input:
1000 479 611 451 936 88 511 364 1 428 412 7 956 490 550 400 317 69 841 240 886 27 133 850 965 631 163 580 771 844 515 244 609 218 86 325 117 943 527 262 581 198 627 238 642 281 93 865 696 295 10 190 89 84 121 223 278 32 985 835 170 525 352 716 213 181 613 153 736 775 370 969 427 272 206 368 945 948 ...
output:
Accepted : 14102
result:
ok
Test #23:
score: 81
Accepted
time: 33ms
memory: 4344kb
input:
999 205 88 976 117 447 358 256 529 787 714 839 326 227 809 265 470 471 196 13 861 689 869 54 157 251 981 668 137 663 555 602 690 442 685 866 857 609 909 760 36 693 316 665 860 456 101 888 782 766 374 928 8 384 771 843 938 318 758 290 215 459 581 532 41 437 881 1 364 762 773 74 749 450 587 550 613 76...
output:
Accepted : 14233
result:
ok
Test #24:
score: 81
Accepted
time: 9ms
memory: 3956kb
input:
513 488 357 44 209 433 49 482 409 3 263 25 348 283 2 423 64 51 231 43 508 6 9 102 236 195 398 276 95 372 391 89 183 125 8 154 203 247 149 217 38 167 416 441 162 467 480 198 26 224 237 320 386 248 377 213 284 435 302 160 473 41 448 259 220 490 496 287 279 507 351 306 298 21 483 392 309 304 312 227 45...
output:
Accepted : 6774
result:
ok
Test #25:
score: 81
Accepted
time: 33ms
memory: 4076kb
input:
979 854 771 54 967 360 412 250 916 832 388 113 939 438 116 138 774 25 142 423 114 440 493 439 375 847 787 215 763 32 681 263 560 567 723 478 684 192 574 728 551 141 647 485 619 829 135 21 156 677 536 247 268 872 1 871 330 941 613 181 806 839 96 150 637 514 467 943 626 697 38 203 564 34 256 705 542 6...
output:
Accepted : 13785
result:
ok
Test #26:
score: 81
Accepted
time: 25ms
memory: 4000kb
input:
923 772 671 235 238 220 356 601 510 445 30 503 48 236 578 364 287 104 632 7 606 474 125 93 622 631 153 274 31 555 741 394 697 52 203 368 586 188 690 643 121 645 854 202 34 21 142 302 508 97 897 264 276 596 90 517 496 895 84 127 469 547 112 366 338 712 833 319 561 482 556 243 462 77 357 704 541 331 7...
output:
Accepted : 13033
result:
ok
Test #27:
score: 81
Accepted
time: 9ms
memory: 4252kb
input:
511 278 368 151 79 471 265 26 375 123 147 35 304 148 382 250 119 354 115 465 331 137 83 187 321 91 94 42 190 270 38 385 52 419 62 95 199 429 309 431 508 313 363 258 455 311 474 459 260 29 195 70 239 101 412 257 421 490 453 332 291 186 440 448 450 248 371 116 377 406 423 192 240 434 327 372 341 100 1...
output:
Accepted : 6675
result:
ok
Test #28:
score: 81
Accepted
time: 34ms
memory: 4040kb
input:
1000 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 92...
output:
Accepted : 14159
result:
ok
Test #29:
score: 81
Accepted
time: 33ms
memory: 3992kb
input:
999 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 ...
output:
Accepted : 14150
result:
ok
Test #30:
score: 81
Accepted
time: 33ms
memory: 4040kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
Accepted : 14159
result:
ok
Extra Test:
score: 0
Extra Test Passed