QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709956 | #6521. Swapping Operation | hhoppitree | WA | 410ms | 4124kb | C++17 | 2.1kb | 2024-11-04 17:38:06 | 2024-11-04 17:38:06 |
Judging History
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];
map< pair<int, int>, int> M;
int calcMax(int x) {
int res = 0;
for (int i = 1; i <= n; ++i) res = max(res, a[i] & x);
return res;
}
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];
}
if (n <= 2000) {
for (int j = x + 1; j <= n; ++j) {
for (int k = x; k < j; ++k) {
res = max(res, (f[k] & a[j]) + g[k + 1]);
}
}
} else {
}
}
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);
}
M.clear();
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, y] : M) {
res = max(res, calcMax(x.first) + x.second);
}
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: 3816kb
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: 55ms
memory: 4104kb
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: 55ms
memory: 3900kb
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: 408ms
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: 410ms
memory: 4060kb
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: 403ms
memory: 3760kb
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: 410ms
memory: 4124kb
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
Wrong Answer
time: 26ms
memory: 3976kb
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:
768093866 978038985 992031499 993520284 984895659 986535974 895984933 992269180 941462284 915450857
result:
wrong answer 1st numbers differ - expected: '990029081', found: '768093866'