QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709909#6521. Swapping OperationhhoppitreeTL 834ms4136kbC++171.7kb2024-11-04 17:21:502024-11-04 17:21:50

Judging History

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

  • [2024-11-04 17:21:50]
  • 评测
  • 测评结果:TL
  • 用时:834ms
  • 内存:4136kb
  • [2024-11-04 17:21:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, a[N], pre[N], nxt[N], res;

void brute() {
    for (int i = 1; i <= n; ++i) {
        pre[i] = (i == 1 ? a[i] : a[i] & pre[i - 1]);
    }
    for (int i = n; i >= 1; --i) {
        nxt[i] = (i == n ? a[i] : a[i] & nxt[i + 1]);
    }
    for (int i = 1; i < n; ++i) {
        res = max(res, pre[i] + nxt[i + 1]);
    }
}

int f[N], g[N];

void calc(int x) {
    if (x == n) return;
    int val = (1 << 30) - 1;
    for (int i = 1; i < x; ++i) val &= a[i];
    f[x] = val;
    for (int i = x + 1; i < n; ++i) {
        f[i] = f[i - 1] & a[i];
    }
    g[n + 1] = a[x];
    for (int i = n; i >= x; --i) {
        g[i] = g[i + 1] & a[i];
    }
    for (int j = 1; j <= n; ++j) {
        for (int k = 1; k < n; ++k) {
            res = max(res, (f[k] & a[j]) + g[k + 1]);
        }
    }
}

void solve(vector<int> pre) {
    for (auto x : pre) calc(x);
}

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        a[0] = a[n + 1] = 0;
        res = 0, brute();
        vector<int> Pre, Nxt;
        for (int i = 1; i <= n; ++i) {
            if (pre[i] != pre[i - 1]) Pre.push_back(i);
            if (nxt[i] != nxt[i + 1]) Nxt.push_back(i);
        }
        solve(Pre);
        reverse(a + 1, a + n + 1);
        for (auto &x : Nxt) x = n - x + 1;
        solve(Nxt);
        for (auto &x : Nxt) x = n - x + 1;
        reverse(a + 1, a + n + 1);
        for (auto x : Pre) {
            for (auto y : Nxt) {
                swap(a[x], a[y]), brute(), swap(a[x], a[y]);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

7
3
3

result:

ok 3 number(s): "7 3 3"

Test #2:

score: 0
Accepted
time: 78ms
memory: 4116kb

input:

1000
100
803046221 177233942 164782937 53823867 383853667 250036100 888743479 576687945 737272231 801579441 647643785 393059353 401516062 663466861 308544510 825328494 162739603 501761995 570908380 655227403 444493122 844535039 208303132 493226172 421479971 634680694 396627047 787471115 335787136 16...

output:

999397418
953601453
996676598
986700621
959469962
997532753
991939977
998064178
992514137
989100873
997784581
990111329
976588292
999515942
997721120
998122389
999751601
995753373
995915998
940455262
994686107
986433302
981799808
992366273
991914073
978772754
993464658
980800625
985148851
993204707
...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 86ms
memory: 3824kb

input:

1000
100
868540859 536350094 243301178 399864672 63800499 60509883 662790489 933274863 712366832 250096549 353585859 849489613 287472674 378377984 318230727 227886897 734961837 146655379 415711604 114613730 147672354 398490255 401593832 198312435 896274101 473745940 345810320 745314936 192335687 317...

output:

993176411
990935453
989361310
998797029
997071496
997847030
993812394
978774674
986546369
979008739
973079854
992485632
996627688
991296275
985058500
982113648
986788726
989529759
991217219
976255336
999106271
983222240
998596661
989428133
995764679
968130163
996135026
975316802
984010492
999825964
...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 827ms
memory: 3836kb

input:

100
1000
536870911 536870911 536870911 53060959 536870911 824976769 536870911 536870911 536870911 536870911 536870911 292812131 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 503316479 536870911 536870911 53...

output:

992267223
998203121
943491181
998903380
991177464
994506493
991568130
996548810
990887537
977900609
996604614
995782790
967198982
986736211
990460937
992025719
999311398
990411560
998302321
992464450
990685689
993256052
994112039
949448278
983078732
996318822
993360844
997651891
993329997
993539076
...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 834ms
memory: 4136kb

input:

100
1000
536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 5...

output:

989528581
993996713
987322111
997982929
998411959
998047555
999898583
983949131
997770426
986856306
986799747
998795930
999640185
984460916
996247390
997607144
996714502
959513743
999472672
988163119
992362297
986480589
999789548
987204597
998918966
999966811
995959839
957028075
977378449
995330581
...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 810ms
memory: 3832kb

input:

100
1000
536870911 536870911 536870911 536870911 536870911 873747431 536870911 536870911 536870911 536870911 336783235 536870911 536870911 536870911 312523694 536870911 4017189 536870911 536870911 536870911 536870911 290368219 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536...

output:

992519359
989582892
989345356
998114450
993532797
989582728
993903109
995936284
996498642
992674823
994002132
994542615
983215409
988921071
999812015
981484433
968086906
998292038
978463424
999965405
980176369
998066264
995426213
972214685
948402982
972799570
997541905
998460289
999426084
995312621
...

result:

ok 100 numbers

Test #7:

score: 0
Accepted
time: 823ms
memory: 4092kb

input:

100
1000
536870911 536870911 536870911 536870911 532704110 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 106395503 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 5...

output:

990153664
981943279
993427066
998331476
975536167
998348971
982632668
951082488
978270675
997843098
996280859
988633268
996123264
997099067
997282090
990623734
990869306
991019882
997017015
998700326
974472542
984414496
992295335
995838763
990083833
963265158
998577560
954058208
991843879
998783291
...

result:

ok 100 numbers

Test #8:

score: -100
Time Limit Exceeded

input:

10
10000
536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 5...

output:


result: