QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#783231	#6256. Deck Randomisation	353cerega^#	AC ✓	19ms	8184kb	C++14	3.1kb	2024-11-26 02:13:15	2024-11-26 02:13:15

Judging History

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

[2024-11-26 02:13:15]
评测

测评结果：AC
用时：19ms
内存：8184kb

查看

[2024-11-26 02:13:15]
提交

answer

#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define X first
#define Y second


const ll mod = 1000000007;
//const ll mod = 998244353;



ll pew(ll a, ll b) {
    ll res = 1;
    while (b>0) {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}


const ll mx = 1000000LL*1000000LL;

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n), b(n), A(n);
    for (ll i=0;i<n;i++) {
        cin >> a[i];
        a[i]--;
    }
    for (ll i=0;i<n;i++) {
        cin >> b[i];
        b[i]--;
    }
    for (ll i=0;i<n;i++) A[i] = b[a[i]];
    ll G = 1;
    vector<ll> was(n);
    for (ll i=0;i<n;i++) {
        if (was[i]==1) continue;
        ll u = i, q = 0;
        while (was[u]==0) {
            was[u] = 1;
            u = A[u];
            q++;
        }
        G = G*q/__gcd(G,q);
        if (G>mx) break;
    }
    ll ans = mx*2+1;
    ans = min(ans,G*2);
    for (ll i=0;i<n;i++) was[i] = 0;
    ll P = 1, r = 0;
    ll F = 0;
    vector<ll> obr(n);
    for (ll i=0;i<n;i++) {
        if (was[i]==1) continue;
        ll u = i;
        vector<ll> ord;
        while (was[u]==0) {
            was[u] = 1;
            obr[u] = ord.size();
            ord.push_back(u);
            u = A[u];
        }
        ll sz = ord.size();
        for (ll x: ord) {
            if (obr[a[x]]==-1) {
                F = 1;
                break;
            }
        }
        if (F==1) break;
        ll r2 = (sz-obr[a[ord[0]]])%sz;
        for (ll j=0;j<sz;j++) {
            if ((obr[a[ord[j]]]+r2)%sz!=j) {
                F = 1;
                break;
            }
        }
        if (F==1) break;
        ll W = sz/__gcd(P,sz);
        ll D = W;
        while (r%sz!=r2 and r<=mx) {
            r += P;
            D--;
            if (D==0) break;
        }
        if (r%sz!=r2) break;
        if (P<=mx) {
            P *= W;
        }
        for (ll j=0;j<sz;j++) {
            obr[ord[j]] = -1;
        }
    }
    if (F==0) {
        ans = min(ans,r*2+1);
    }
    if (ans>mx) {
        cout << "huge\n";
        return;
    }
    /*if (ans%2==1) {
        ll W = ans/2;
        vector<ll> cur = a;
        while (W>0) {
            if (W&1) {
                vector<ll> nxt(n);
                for (ll i=0;i<n;i++) nxt[i] = A[cur[i]];
                cur = nxt;
            }
            W >>= 1;
            {
                vector<ll> nxt(n);
                for (ll i=0;i<n;i++) nxt[i] = A[A[i]];
                A = nxt;
            }
        }
        ll ok = 1;
        for (ll i=0;i<n;i++) {
            if (A[i]!=i) {
                ok = 0;
            }
        }
        if (ok!=1) {
            cout << "huge\n";
            return;
        }
    }*/
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3656kb

input:

3
2 3 1
3 1 2

output:

result:

ok single line: '2'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

6
5 1 6 3 2 4
4 6 5 1 3 2

output:

result:

ok single line: '5'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

8
1 4 2 6 7 8 5 3
3 6 8 4 7 1 5 2

output:

result:

ok single line: '10'

Test #4:

score: 0

Accepted

time: 19ms

memory: 8064kb

input:

100000
3579 88291 72914 52941 71563 36997 805 53539 87847 31762 62083 49901 40952 79578 7702 29574 4243 8890 20174 25838 43055 17844 90086 94709 20204 71003 42093 50724 57605 73490 57193 50830 66768 84400 31603 32471 23127 30429 42643 97110 84418 24927 89341 16047 37795 50780 55098 56830 28698 12114...

output:

result:

ok single line: '199999'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

3
2 3 1
2 3 1

output:

result:

ok single line: '3'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

1
1
1

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 16ms

memory: 7068kb

input:

100000
36570 54476 88856 18970 98842 52271 51747 78828 25681 75300 18197 27262 63840 54184 58777 21907 51270 5097 57777 28111 63073 73699 69757 41713 70600 84384 8683 64033 43647 4438 42029 72101 71035 70442 16316 52611 56678 84611 28731 44331 10051 1449 26820 58460 83797 22780 51171 13691 85995 611...

output:

999999999999

result:

ok single line: '999999999999'

Test #8:

score: 0

Accepted

time: 12ms

memory: 7164kb

input:

100000
25973 37824 67053 56973 4331 76510 69708 82710 15468 27346 21484 24028 98043 23037 54673 56688 58661 49507 230 32090 90307 5548 13903 84069 93300 20539 9585 67982 34975 16557 61339 62628 19559 25420 4636 66942 74445 40139 56867 70900 50421 19431 57528 88782 89912 26983 70452 76236 70070 82967...

output:

result:

ok single line: '24691'

Test #9:

score: 0

Accepted

time: 12ms

memory: 7024kb

input:

100000
89584 40440 82767 63944 37022 65779 22340 10327 21597 55271 5411 77841 82730 44188 66384 54644 29326 10646 31802 66277 94178 45308 60298 27207 30551 59019 29107 26519 2750 95437 20877 70822 41384 36434 46329 52953 47421 28148 82707 79107 51346 27572 21623 52873 22740 64975 6183 47363 2020 229...

output:

huge

result:

ok single line: 'huge'

Test #10:

score: 0

Accepted

time: 12ms

memory: 7080kb

input:

100000
71906 59773 37202 15876 89320 13047 70090 61374 97295 53499 59413 66854 94074 10502 55724 67194 49000 1073 61380 41311 18039 25683 40213 56557 96700 6464 7889 80124 22904 47592 38486 13774 66270 24390 32135 74050 71858 28629 82485 99306 57997 71170 88883 23605 53589 24674 6689 63157 88506 557...

output:

huge

result:

ok single line: 'huge'

Test #11:

score: 0

Accepted

time: 13ms

memory: 7208kb

input:

100000
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:

huge

result:

ok single line: 'huge'

Test #12:

score: 0

Accepted

time: 2ms

memory: 4016kb

input:

10000
6602 2237 9260 1171 2372 5342 7083 1352 7459 3284 5927 6514 5425 7302 8076 6004 8759 6294 3973 1725 5312 9897 3257 6965 1332 4193 4844 4919 9826 6962 7738 521 2731 2972 6521 9133 6148 9304 5975 3368 6447 985 8024 9223 9960 1078 1798 9974 9731 3052 6426 4783 3514 9078 9345 6818 4725 7611 3179 8...

output:

result:

ok single line: '2675'

Test #13:

score: 0

Accepted

time: 2ms

memory: 4116kb

input:

10000
3085 3768 5941 6818 1888 3067 185 1492 4543 1313 2703 8492 4110 8668 5824 158 9388 6552 2485 8474 760 2499 5958 7206 5206 8350 461 8324 529 2884 8432 6190 8226 4238 9836 1960 949 9529 1980 6286 7171 1211 9855 2453 4897 7827 8536 5461 4461 2390 5868 1669 6470 1831 2584 6335 334 9635 7409 7293 4...

output:

huge

result:

ok single line: 'huge'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

1000
779 778 293 143 68 908 512 952 152 865 845 534 574 967 813 885 177 483 166 43 338 275 59 547 750 26 228 530 556 817 117 454 913 17 933 792 742 536 149 204 284 42 104 431 404 774 780 30 31 930 308 636 786 312 924 442 455 744 135 384 430 480 446 109 630 335 526 475 214 961 206 929 256 804 854 279...

output:

result:

ok single line: '841'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

100
42 90 27 10 25 1 76 7 82 79 50 26 95 89 3 30 60 93 73 65 51 22 74 21 80 69 45 36 54 56 100 16 94 39 87 99 38 83 48 97 20 70 24 66 15 34 8 46 63 91 43 49 28 17 33 32 12 14 11 29 67 71 88 86 72 81 64 5 57 6 2 41 92 35 55 47 58 44 85 68 78 13 96 19 98 61 23 52 77 62 59 84 18 75 9 37 31 4 53 40
51 1...

output:

result:

ok single line: '139'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3872kb

input:

10
10 5 3 6 4 9 1 2 7 8
10 5 3 6 4 9 1 2 7 8

output:

result:

ok single line: '9'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3568kb

input:

10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

output:

result:

ok single line: '1'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

10
1 2 3 4 5 6 7 8 9 10
9 8 6 10 3 4 7 2 5 1

output:

result:

ok single line: '1'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

10
9 8 6 10 3 4 7 2 5 1
1 2 3 4 5 6 7 8 9 10

output:

result:

ok single line: '27'

Test #20:

score: 0

Accepted

time: 4ms

memory: 4344kb

input:

22014
8983 10808 7878 16931 6588 17783 16680 579 12390 17198 9090 3072 3831 21499 15241 4397 12396 3013 21847 10173 2224 7891 18858 16769 1014 16154 7664 11018 5175 937 3100 4883 12231 12336 12583 18838 10591 21027 5475 17296 14378 18363 700 2096 57 8084 10079 18616 5177 3398 13531 20210 8317 6557 1...

output:

result:

ok single line: '3'

Test #21:

score: 0

Accepted

time: 2ms

memory: 4396kb

input:

12030
2709 9375 11172 966 11728 8750 5771 8637 853 1308 579 2097 7355 1645 8409 2150 6124 7050 9293 482 9383 3482 7933 1561 10851 701 739 7522 1706 7452 615 122 7990 6457 5372 2691 3965 2157 4389 3472 5030 2620 11705 11405 6398 8512 4803 10685 6986 10838 5462 9172 11112 9842 7457 5547 9489 6106 2853...

output:

46282331503

result:

ok single line: '46282331503'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3864kb

input:

130
104 130 31 122 94 20 59 29 120 84 54 127 50 108 93 70 13 2 24 71 75 106 56 81 19 17 129 69 1 126 62 22 114 5 43 97 64 65 99 9 38 51 34 66 44 113 40 47 105 67 80 87 63 82 95 39 85 72 117 111 74 109 45 76 57 116 16 103 46 23 28 110 89 101 48 119 83 98 90 115 58 92 86 37 88 60 14 42 26 128 36 15 12...

output:

result:

ok single line: '1797'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

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

output:

result:

ok single line: '27'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

15
13 14 8 10 15 7 4 3 1 9 5 12 6 2 11
10 2 3 6 5 1 13 8 4 7 11 12 9 14 15

output:

result:

ok single line: '59'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

2
1 2
1 2

output:

result:

ok single line: '1'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

2
1 2
2 1

output:

result:

ok single line: '1'

Test #27:

score: 0

Accepted

time: 0ms

memory: 3888kb

input:

2
2 1
1 2

output:

result:

ok single line: '3'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

2
2 1
2 1

output:

result:

ok single line: '2'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3556kb

input:

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

output:

result:

ok single line: '31'

Test #30:

score: 0

Accepted

time: 0ms

memory: 3856kb

input:

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

output:

result:

ok single line: '115'

Test #31:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

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

output:

result:

ok single line: '9'

Test #32:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

5
4 2 5 3 1
5 2 4 1 3

output:

result:

ok single line: '2'

Test #33:

score: 0

Accepted

time: 7ms

memory: 6568kb

input:

65536
47955 6883 45137 25439 27440 9624 18098 48181 34426 1820 15683 21406 64870 27104 43347 4835 28446 23355 63205 44473 6295 50577 43727 20888 29274 27677 51878 49188 4623 63055 7267 45997 58185 34509 63765 40454 52147 46349 58392 32992 18834 29333 26926 39368 34863 51258 29060 9339 4780 43091 177...

output:

result:

ok single line: '131072'

Test #34:

score: 0

Accepted

time: 7ms

memory: 6496kb

input:

65536
29296 28050 62777 16586 28123 22438 9316 6641 57704 64498 49698 12373 16198 38922 43547 10904 35079 56083 517 28611 6819 25078 2923 22502 3836 30674 15310 33050 6165 22940 54788 20584 3630 47499 36453 10653 54714 16224 59964 39340 58504 23095 9934 35754 22290 20679 9574 135 26415 58787 44022 2...

output:

result:

ok single line: '9135'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

6
4 5 2 6 3 1
5 2 3 4 6 1

output:

result:

ok single line: '8'

Test #36:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

7
6 5 2 4 7 3 1
5 6 2 3 4 1 7

output:

result:

ok single line: '8'

Test #37:

score: 0

Accepted

time: 14ms

memory: 7732kb

input:

85541
18271 18138 978 45960 70031 42087 17841 59367 933 64053 36577 67717 7193 29429 25252 53404 73979 76566 18032 6333 22398 34554 20597 12060 49524 27701 36429 1438 54108 17086 45933 22699 75472 41286 19068 75764 32350 18126 58029 75372 57784 41009 15502 29311 9696 28373 41058 75996 23743 78431 77...

output:

result:

ok single line: '171082'

Test #38:

score: 0

Accepted

time: 15ms

memory: 7472kb

input:

85541
11480 872 47288 6899 24223 4549 12109 49598 49785 61410 19024 48963 59507 68614 57118 20524 47462 83178 58076 76158 59107 80210 45823 77707 65685 15796 31114 49031 70802 62690 30425 40965 40836 13144 4021 33637 82209 66802 68010 11790 8039 55619 50164 25132 33836 85215 578 55529 53892 81122 39...

output:

result:

ok single line: '104723'

Test #39:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

8
2 5 6 7 4 8 3 1
2 4 1 6 3 8 5 7

output:

result:

ok single line: '30'

Test #40:

score: 0

Accepted

time: 14ms

memory: 8104kb

input:

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

output:

huge

result:

ok single line: 'huge'

Test #41:

score: 0

Accepted

time: 12ms

memory: 7040kb

input:

99900
2 1 4 5 3 7 8 9 10 6 12 13 14 15 16 17 11 19 20 21 22 23 24 25 26 27 28 18 30 31 32 33 34 35 36 37 38 39 40 41 29 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 42 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 59 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 78 10...

output:

huge

result:

ok single line: 'huge'

Test #42:

score: 0

Accepted

time: 8ms

memory: 8080kb

input:

99991
94521 85417 59143 81624 48244 77871 75754 82785 91385 86278 86288 72693 4620 29429 27839 27713 899 73775 42119 60003 16103 30033 74711 68687 94553 19835 57001 90325 95207 62556 65097 23795 25884 58633 2592 84702 23862 68366 28365 14742 10986 39419 47754 62607 98933 45798 99597 49618 12713 9667...

output:

result:

ok single line: '199982'

Test #43:

score: 0

Accepted

time: 10ms

memory: 8184kb

input:

99991
3274 56021 14320 9986 74208 70639 6694 43067 58657 55169 65081 70778 58979 73639 79198 28089 85160 31240 899 80977 64160 67524 74512 55134 20388 84359 14578 74930 10027 58819 82532 514 37890 77564 83157 82002 33886 9557 79644 16412 86836 61778 67818 26538 16442 93662 6960 32132 6506 76739 7864...

output:

result:

ok single line: '9135'