QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#315265#8166. Almost Largeucup-team1430#AC ✓403ms45756kbC++202.3kb2024-01-27 09:54:532024-01-27 09:54:53

Judging History

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

  • [2024-01-27 09:54:53]
  • 评测
  • 测评结果:AC
  • 用时:403ms
  • 内存:45756kb
  • [2024-01-27 09:54:53]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()
#define sws cin.tie(0)->sync_with_stdio(false);
#define endl '\n'

using namespace std;

const ll MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;

#define bt array<int, 12>

bt num_to_bits(int x) {
    bt ans = {0};
    int id = 0;
    while (x > 0) {
        ans[id++] = x % 3;
        x /= 3;
    }
    return ans;
}

int bits_to_num(bt x) {
    int ans = 0;
    for (int i=11;i>=0;i--) {
        ans *= 3;
        ans += x[i];
    }
    return ans;
}

int32_t main() {
    #ifndef LOCAL
    sws;
    #endif

    int n; cin >> n;
    vector<int> a(n);
    const int MAX = 531441 + 10;
    for (int i=0;i<n;i++) {
        cin >> a[i];
    }

    vector<vector<int>> hooks(MAX);

    for (int id=0;id<n-1;id++) {
        bt bi = num_to_bits(a[id]);
        for (int i=0;i<12;i++) {
            for (int j=0;j<2;j++) {
                if (bi[i] <= j) continue;
                bt bi2 = bi;
                bi2[i] = j;
                int biv = bits_to_num(bi2);
                hooks[biv].push_back(id);
                // cout << "hooks = " << id << endl;
            }
        }
    }

    queue<int> q;
    vector<bool> visto(MAX, false);
    q.push(a[n-1]);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (visto[u]) continue;
        visto[u] = true;
        for (auto v2: hooks[u]) q.push(a[v2]);
        bt bu = num_to_bits(u);
        for (int i=0;i<12;i++) {
            if (bu[i] == 0) continue;
            bt bu2 = bu; bu2[i] --;
            int v = bits_to_num(bu2);
            q.push(v);
        }
    }

    // for (int i=0;i<30;i++) {
    //     cout << i << " = " << visto[i] << endl;
    // }

    cout << (visto[a[0]] ? "Yes":"No") << endl;







    // bt x = num_to_bits(21);
    // for (int i=0;i<12;i++) {
    //     cout << (int)x[i] << " ";
    // }
    // cout << endl;

    // cout << bits_to_num(x) << endl;
    


    return 0;
}

// ulimit -s unlimited
// alias comp="g++ -std=c++20 -O2 -o out"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 15692kb

input:

2
21 14

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 3ms
memory: 15656kb

input:

2
12 1

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 4ms
memory: 15744kb

input:

5
5 15 45 135 405

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 288ms
memory: 38684kb

input:

133729
515927 251707 509591 317498 177389 461753 275297 7848 452936 13695 394604 125096 242390 450018 501210 126212 64950 263819 216408 528515 454055 530346 241575 397712 524748 322154 60967 469683 464304 390612 215474 271893 127704 380804 390268 391984 401683 315101 523057 462146 194859 259610 4680...

output:

Yes

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 261ms
memory: 39960kb

input:

147249
527398 156678 5013 10368 17399 404399 217450 522971 155321 137708 345490 200329 199022 345117 528603 317293 67005 130459 30924 64105 394479 346479 136837 348286 469655 20584 530096 17403 74005 411855 519402 345524 406285 466066 155362 336093 353489 89402 215173 316455 86564 219312 275911 5142...

output:

Yes

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 278ms
memory: 39744kb

input:

154864
161885 172921 134934 393030 407706 454939 472219 487595 306439 302673 133875 490411 160434 294750 302400 459353 126961 297736 516062 411665 526210 281273 488744 411552 258834 79760 153295 463225 334602 395999 260123 127474 332557 456901 368795 432484 340435 478696 373285 115549 76099 174426 1...

output:

Yes

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 161ms
memory: 28124kb

input:

63572
336255 347207 500607 340509 391257 233454 476378 424093 91856 141952 452955 247724 466197 406255 62549 292873 4013 335193 254192 62977 52420 245444 520397 513186 246995 291290 40810 273443 136933 375866 192240 81675 276874 314671 330546 350403 28320 355536 389101 86751 300940 10450 299066 3188...

output:

Yes

result:

ok answer is YES

Test #8:

score: 0
Accepted
time: 171ms
memory: 28732kb

input:

63829
316865 74162 324739 305131 229923 463058 279311 237746 28582 257558 206932 447230 202462 181752 372628 469925 530359 361909 16297 99464 441119 451838 80051 443822 357373 378963 229930 515212 480614 184350 221515 327085 339769 407134 318770 179961 50736 55318 522509 355408 229777 212902 59870 4...

output:

Yes

result:

ok answer is YES

Test #9:

score: 0
Accepted
time: 173ms
memory: 28968kb

input:

66300
498574 249399 472527 39518 368230 401160 286065 203002 203380 390080 472426 243647 413311 318083 505420 10196 213875 36281 50044 104900 285602 505210 446922 393346 472415 344244 252238 298178 281757 502751 328216 308348 91687 194157 304780 314634 292092 255665 354178 20507 404232 82270 174 655...

output:

Yes

result:

ok answer is YES

Test #10:

score: 0
Accepted
time: 55ms
memory: 23832kb

input:

66115
62089 450098 41561 191728 39886 311800 521782 308368 148534 170885 267088 327438 444016 73879 170891 526128 262015 209834 203906 252727 428679 507414 265655 303411 295759 106683 528647 128909 417598 20174 83715 474612 93617 83592 516378 417746 290446 292113 48384 145560 192004 393050 52252 109...

output:

No

result:

ok answer is NO

Test #11:

score: 0
Accepted
time: 49ms
memory: 23124kb

input:

53788
420916 157883 340502 18615 88238 449119 246036 244635 404627 512930 506346 514674 356674 402440 120570 156822 118152 41839 138733 256798 281838 121047 16425 376388 511313 103964 380932 115266 924 62074 177569 265724 358136 417402 223292 324569 399208 247245 183715 338535 458902 191058 319308 3...

output:

No

result:

ok answer is NO

Test #12:

score: 0
Accepted
time: 63ms
memory: 27232kb

input:

91639
418076 40193 213136 40918 398440 48622 264979 280637 260361 224127 74066 275916 429505 14185 183468 259153 461015 20091 253894 79106 472110 245549 284748 104215 269369 42046 430809 422216 94315 457526 390666 471060 99034 50627 417025 2351 357866 365412 382166 187616 37592 225668 274396 72129 3...

output:

No

result:

ok answer is NO

Test #13:

score: 0
Accepted
time: 63ms
memory: 25296kb

input:

58160
292385 285328 199656 167096 225767 492816 494905 120456 435730 124311 21606 439375 474228 54926 53573 178017 474714 405869 24514 172817 351500 345523 121821 401581 518332 242361 170395 467765 142918 296769 115136 468977 82819 141450 137967 438784 113558 54050 379968 83698 401794 63972 353870 2...

output:

No

result:

ok answer is NO

Test #14:

score: 0
Accepted
time: 57ms
memory: 26220kb

input:

65650
86662 382083 44859 452176 87562 304759 6870 59607 465941 463033 241293 493000 62436 312824 285685 479424 128945 432211 515232 23525 88853 217640 458938 255273 75281 238467 432052 388472 64356 157854 83497 141453 157856 407903 405805 462655 300988 462998 102980 380738 328896 263925 238126 26624...

output:

No

result:

ok answer is NO

Test #15:

score: 0
Accepted
time: 57ms
memory: 24388kb

input:

53286
353564 67122 318031 452393 62410 295035 240007 487333 510207 14158 443924 317573 443166 501387 246243 118638 52368 156680 390419 103859 294785 35097 482647 252085 72802 347577 214612 487162 126802 361380 1425 116169 24848 169657 405753 119947 309884 149273 155193 156725 470464 246090 334572 22...

output:

No

result:

ok answer is NO

Test #16:

score: 0
Accepted
time: 65ms
memory: 18380kb

input:

2
0 531440

output:

Yes

result:

ok answer is YES

Test #17:

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

input:

2
531440 0

output:

No

result:

ok answer is NO

Test #18:

score: 0
Accepted
time: 403ms
memory: 45756kb

input:

200000
374417 29016 240451 31361 407954 382411 67705 444674 321056 357704 99124 162344 101180 287550 363934 1539 162478 90600 64207 387137 267614 62632 405525 174849 325065 306139 400140 329097 223126 216010 475126 187908 137500 411022 444490 247612 260513 117375 78523 466080 294480 435078 122714 29...

output:

Yes

result:

ok answer is YES

Test #19:

score: 0
Accepted
time: 67ms
memory: 17956kb

input:

25
531440 265720 199021 206662 464738 462551 464741 442868 199018 1 265711 206392 206419 531431 472139 177148 472112 465551 465470 265721 199831 472382 199750 196831 0

output:

Yes

result:

ok answer is YES

Test #20:

score: 0
Accepted
time: 329ms
memory: 41604kb

input:

162129
270979 282339 431424 425460 252800 274304 388682 393864 416562 480571 199401 312490 253860 436227 466797 191773 86553 174892 40460 76017 455956 325489 403510 242426 79223 220924 307934 290894 336292 292065 360778 214929 300605 309077 91771 325897 367654 46606 411598 10487 93572 226939 318222 ...

output:

Yes

result:

ok answer is YES

Test #21:

score: 0
Accepted
time: 303ms
memory: 40224kb

input:

134439
489459 3233 521415 465639 132850 177128 62184 131496 259564 389730 186837 82838 101963 108924 178291 357234 173405 197483 137114 203789 407677 257378 305151 270692 362211 211260 300447 384866 333487 376328 294813 405421 316753 437092 100158 418391 377131 367300 14448 509243 448136 212450 8968...

output:

Yes

result:

ok answer is YES

Test #22:

score: 0
Accepted
time: 244ms
memory: 39148kb

input:

120909
332651 70836 216408 226582 317929 191883 193609 136988 494304 223256 517406 234640 121643 205327 63712 386452 505802 38063 271162 307046 394343 440055 283696 438543 130400 478974 253391 34479 364064 494886 330303 464487 110199 514589 395192 517328 515744 47165 375715 271566 148169 352606 2487...

output:

Yes

result:

ok answer is YES

Test #23:

score: 0
Accepted
time: 232ms
memory: 37060kb

input:

100451
234622 272121 473113 459149 15567 403310 442188 199036 299205 115037 393431 92090 302194 188543 401262 256320 399679 444178 68376 436825 241220 298022 477173 455536 408784 94274 477770 194505 480640 309655 480833 313851 63388 134715 77580 85871 7566 450734 508008 306800 80497 23585 245001 161...

output:

Yes

result:

ok answer is YES

Test #24:

score: 0
Accepted
time: 234ms
memory: 36280kb

input:

106576
408195 521739 268706 344196 89524 8889 336379 485723 505658 144713 317423 285344 401217 246883 358899 137501 186387 209384 486181 373787 144710 423375 68686 225060 494788 441592 507285 291838 317216 232858 63120 381639 380162 134258 528209 218332 272470 38847 289516 369072 358241 511276 28074...

output:

Yes

result:

ok answer is YES

Test #25:

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

input:

40
203911 155566 279357 96772 292487 123358 314134 131692 251008 232213 358632 333713 402334 116925 288905 215453 147433 385591 188038 116516 297705 484172 120604 87267 46804 134399 421603 310735 136987 295770 280637 364227 401119 216661 193401 334285 353151 5318 166916 116390

output:

No

result:

ok answer is NO

Test #26:

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

input:

43
48515 239556 56760 299254 302691 9532 375783 80363 39633 261330 527719 424425 97088 265731 461869 399137 245937 344660 7710 113318 343760 456228 238126 113770 130905 472815 75126 441318 514897 154195 27860 97560 515051 285092 414070 250284 431837 9489 302876 256495 188630 512152 209118

output:

No

result:

ok answer is NO

Test #27:

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

input:

9
198429 281253 78301 397307 130115 157743 52845 253131 130781

output:

No

result:

ok answer is NO

Test #28:

score: 0
Accepted
time: 3ms
memory: 15812kb

input:

12
39777 42099 21927 22491 22494 39909 39588 42204 41718 41853 44016 22308

output:

Yes

result:

ok answer is YES

Test #29:

score: 0
Accepted
time: 3ms
memory: 15608kb

input:

73
218862 338337 453519 40824 419256 161109 219591 202014 237087 80352 83997 62856 24138 474579 24219 376245 42363 43740 256689 277101 320193 261873 474660 458541 810 334611 418446 4455 415530 255960 62775 377784 474012 200637 103599 179496 417069 59049 340605 340524 45279 257418 516132 298242 14013...

output:

Yes

result:

ok answer is YES

Test #30:

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

input:

14
118128 485517 413349 242844 249453 479094 124686 59190 472398 242790 413505 413511 360858 65670

output:

Yes

result:

ok answer is YES

Test #31:

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

input:

8
65706 119688 237039 13191 428010 59064 73020 426513

output:

No

result:

ok answer is NO

Test #32:

score: 0
Accepted
time: 3ms
memory: 15672kb

input:

50
5355 205407 219708 221634 21654 365976 4914 207810 180585 227700 217071 398097 42813 386919 210492 11925 204174 412614 32625 14643 216270 191754 215325 10278 43038 380079 367173 410454 203166 368415 382032 185958 405090 389304 29457 356760 225531 43749 216306 197145 33786 360918 370881 28008 1915...

output:

Yes

result:

ok answer is YES

Test #33:

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

input:

93
118118 133326 421624 480106 126531 296219 428249 120062 185094 119485 177894 14663 8525 177157 414317 354638 303202 132122 360855 250382 133003 413768 72838 61012 420552 487235 185573 243244 413849 178281 132365 421445 66764 309916 250777 250867 13448 190512 61165 362090 310149 184043 14824 1 473...

output:

No

result:

ok answer is NO

Extra Test:

score: 0
Extra Test Passed