QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#122001 | #6521. Swapping Operation | Sorting | WA | 56ms | 14132kb | C++20 | 4.9kb | 2023-07-09 02:36:54 | 2023-07-09 02:36:56 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <utility>
#include <array>
using namespace std;
#define all(x) (x).begin(), (x).end()
const int N = 1e5 + 3;
const int LOGN = 20;
int n, a[N], mask, add;
vector<int> important, answers;
int up[LOGN][N], _log[N];
void init(){
for(int i = 1; i <= n; ++i)
up[0][i] = i;
for(int j = 1; j < LOGN; ++j){
for(int i = 1; i <= n; ++i){
up[j][i] = up[j - 1][i] & up[j - 1][min(i + (1 << (j - 1)), n)];
}
}
for(int i = 1; i <= n; ++i)
_log[i] = 0;
for(int i = 2; i <= n; i *= 2)
_log[i]++;
for(int i = 1; i <= n; ++i)
_log[i] += _log[i - 1];
}
int and_query(int l, int r){
if(l > r)
return (1 << 30) - 1;
int dist = r - l + 1;
int log_d = _log[dist];
return up[log_d][l] & up[log_d][r - (1 << log_d) + 1];
}
bool check(int new_mask){
for(int x: answers){
if((new_mask & x) == new_mask)
return true;
}
static int prefix[N], suffix[N];
prefix[1] = a[1] & new_mask;
suffix[n] = a[n] & new_mask;
for(int i = 2; i <= n; ++i)
prefix[i] = prefix[i - 1] & a[i];
for(int i = n - 1; i >= 1; --i)
suffix[i] = suffix[i + 1] & a[i];
static int cnt[N];
for(int i = 1; i <= n; ++i)
cnt[i] = cnt[i - 1] + ((a[i] & new_mask) == new_mask);
auto get_cnt = [&](int l, int r){
return cnt[r] - cnt[l - 1];
};
for(int i = 1; i < n; ++i){
int common = (new_mask ^ prefix[i]) & (new_mask ^ suffix[i + 1]);
for(int x: important){
if(x > i) continue;
if(!get_cnt(i + 1, n)) continue;
int l = and_query(1, x - 1) & and_query(x + 1, i) & new_mask;
int r = a[x] & and_query(i + 1, n) & new_mask;
if(l + r == new_mask){
return true;
}
}
}
for(int i = 1; i < n; ++i){
int common = (new_mask ^ prefix[i]) & (new_mask ^ suffix[i + 1]);
for(int x: important){
if(x <= i) continue;
if(!get_cnt(1, i)) continue;
int l = and_query(i + 1, x - 1) & and_query(x + 1, n) & new_mask;
int r = a[x] & and_query(1, i) & new_mask;
if(l + r == new_mask){
return true;
}
}
}
return false;
}
int do_alg(){
static int prefix[N], suffix[N];
prefix[1] = a[1] & mask;
suffix[n] = a[n] & mask;
for(int i = 2; i <= n; ++i)
prefix[i] = prefix[i - 1] & a[i];
for(int i = n - 1; i >= 1; --i)
suffix[i] = suffix[i + 1] & a[i];
int ans = 0;
for(int i = 1; i <= n - 1; ++i)
ans = max(ans, prefix[i] + suffix[i + 1]);
return ans;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
init();
mask = 0;
add = 0;
important.clear();
answers.clear();
for(int bit = 0; bit < 30; ++bit){
int cnt = 0;
for(int i = 1; i <= n; ++i){
cnt += a[i] >> bit & 1;
}
if(cnt == 0){
}
else if(cnt == n - 1)
add += 1 << bit;
else if(cnt == n)
add += (1 << bit) * 2;
else{
mask += 1 << bit;
}
}
// cout << "add " << add << endl;
for(int j = 0; j < 30; ++j){
if(!(mask >> j & 1))
continue;
int first = -1, last = -1;
for(int i = 1; i <= n; ++i){
if(a[i] >> j & 1){
if(first == -1)
first = i;
last = i;
}
}
important.push_back(first);
important.push_back(last);
}
sort(all(important));
important.resize(unique(all(important)) - important.begin());
for(int i = 0; i < important.size(); ++i){
for(int j = i + 1; j < important.size(); ++j){
int x = important[i];
int y = important[j];
swap(a[x], a[y]);
int ans = do_alg();
swap(a[x], a[y]);
answers.push_back(ans);
}
}
int new_mask = 0;
for(int bit = 29; bit >= 0; --bit){
if(!(mask >> bit & 1))
continue;
if(check(new_mask + (1 << bit))){
new_mask += 1 << bit;
}
}
// cout << "important" << " ";
// for(int x: important)
// cout << x << " ";
// cout << "\n";
// cout << "add " << add << "\n";
cout << new_mask + add << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11652kb
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: 56ms
memory: 13664kb
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: 56ms
memory: 11728kb
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: 13ms
memory: 11648kb
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: 26ms
memory: 11636kb
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: 26ms
memory: 11740kb
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: 21ms
memory: 11820kb
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: 0
Accepted
time: 16ms
memory: 11984kb
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:
990029081 996941040 996327033 997094193 990980188 986535974 995007098 992269180 986003383 990736573
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 20ms
memory: 11988kb
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:
998160970 962252371 994002209 991351157 989772171 995168012 992749639 979618052 993648300 994703533
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 16ms
memory: 11796kb
input:
10 10000 536870911 536870911 536870911 536870911 536870911 16495861 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 53...
output:
985813020 994294933 997857971 993640204 986032808 998285161 983501855 971946900 956658469 999420409
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 26ms
memory: 11792kb
input:
10 10000 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 313408423 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 536870911 313570023 536870911 536870911 536870911 5...
output:
982812296 997742114 981766884 999744972 997761413 998863157 985723058 993661054 978461035 988009489
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 13ms
memory: 14132kb
input:
1 100000 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:
972405752
result:
ok 1 number(s): "972405752"
Test #13:
score: 0
Accepted
time: 18ms
memory: 13916kb
input:
1 100000 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:
998689648
result:
ok 1 number(s): "998689648"
Test #14:
score: 0
Accepted
time: 27ms
memory: 13960kb
input:
1 100000 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:
994388419
result:
ok 1 number(s): "994388419"
Test #15:
score: 0
Accepted
time: 19ms
memory: 13976kb
input:
1 100000 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:
989540923
result:
ok 1 number(s): "989540923"
Test #16:
score: 0
Accepted
time: 42ms
memory: 11824kb
input:
100 1000 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 837325606 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 32767 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 126115569 1...
output:
982308028 996564253 996609583 997022165 999374550 985361560 999478520 993722720 991250154 979352632 986662229 941977900 994874484 987631482 986434267 992081760 983067730 981143075 960913139 968402815 977588561 994831317 974612625 988674180 999955804 997471683 999190084 998157218 989508864 990923047 ...
result:
ok 100 numbers
Test #17:
score: 0
Accepted
time: 36ms
memory: 11784kb
input:
100 1000 616268620 1048575 1048575 1048575 452541743 1048575 1048575 1048575 1048575 1048575 1048575 606479664 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048575 363441026 1048575 1048575 1048575 1048575 1048575 1048575 1048575 1048063 1048575 1048575 104...
output:
996150731 984809627 995669944 982030168 991635773 993567985 997822209 991209301 981201290 998182500 997161166 981475211 992222302 996125404 991731823 996458082 992441428 986905918 980110015 994853843 994902592 987967626 997935529 993287385 978588380 994185418 992141092 998867415 993128068 998901163 ...
result:
ok 100 numbers
Test #18:
score: 0
Accepted
time: 36ms
memory: 11680kb
input:
100 1000 65535 618316639 65535 65535 993627304 380378305 65535 65535 65535 945385481 65535 65535 65535 65535 65535 65535 79411578 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 914329319 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65527 65535 65535 65535 65535 65535 6553...
output:
993627304 997223787 995172986 967820232 922402818 997535890 993611366 992655911 990088233 974096338 991520197 994247557 986080004 988680068 999969094 989722792 993034847 997733224 981663826 999346544 988286385 985827812 998217951 996190322 997875057 990266756 961958261 999840457 997202565 965336151 ...
result:
ok 100 numbers
Test #19:
score: 0
Accepted
time: 38ms
memory: 13788kb
input:
100 1000 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 965746870 65535 65535 26067041 65535 65535 65535 65535 65535 65535 65407 815280236 65535 65535 65535 65535 65535 65535 141975591 31573753 65535 65535 65535 65535 65535 65535 65535 65535 65535 714044884 65535 65535 65535 65535 65535...
output:
994767992 999418764 999595232 989253454 995703749 995109821 995572054 998158226 998824617 993115590 995195933 998165626 988778437 999809543 999050273 989769941 988127888 997869761 973559942 976992249 983966156 994286226 985631965 999385566 999168590 991878403 990876708 997710130 998254097 975887194 ...
result:
ok 100 numbers
Test #20:
score: 0
Accepted
time: 40ms
memory: 13856kb
input:
10 10000 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 655...
output:
979181468 995314897 999891673 994759732 995272120 991865668 990726455 993478676 992528987 987220465
result:
ok 10 numbers
Test #21:
score: 0
Accepted
time: 36ms
memory: 11844kb
input:
10 10000 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 655...
output:
959263243 991996367 995991242 997110748 948361300 977587814 974675025 993689915 983580122 999288163
result:
ok 10 numbers
Test #22:
score: 0
Accepted
time: 28ms
memory: 11868kb
input:
10 10000 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 33554431 335...
output:
998080400 988696279 994030605 985117297 977015987 993716359 994170126 992382439 997862873 992083867
result:
ok 10 numbers
Test #23:
score: 0
Accepted
time: 24ms
memory: 12040kb
input:
10 10000 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 2...
output:
993892148 982630093 970910815 997072305 976510027 997040055 985100681 996417543 995614901 995181841
result:
ok 10 numbers
Test #24:
score: 0
Accepted
time: 28ms
memory: 13960kb
input:
1 100000 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 2...
output:
989497980
result:
ok 1 number(s): "989497980"
Test #25:
score: 0
Accepted
time: 32ms
memory: 13996kb
input:
1 100000 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 2...
output:
985741038
result:
ok 1 number(s): "985741038"
Test #26:
score: 0
Accepted
time: 13ms
memory: 13944kb
input:
1 100000 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 2...
output:
999945210
result:
ok 1 number(s): "999945210"
Test #27:
score: 0
Accepted
time: 33ms
memory: 14072kb
input:
1 100000 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 268435455 2...
output:
967682724
result:
ok 1 number(s): "967682724"
Test #28:
score: -100
Wrong Answer
time: 24ms
memory: 11616kb
input:
2000 50 368834445 502136717 402515949 99477359 402253581 368701357 368705535 401473453 268433183 132906943 401340269 502263599 236919675 367785869 100394767 367914765 535691229 234743695 367650621 401205103 367912781 99477439 401604399 502917103 502265805 133955453 134213439 267787059 240623442 2469...
output:
535691997 536779215 536788603 536800399 536870509 537921287 533715579 539191097 536862345 534249350 536609029 536709016 536608483 542065355 536858821 536861196 536458027 535600908 536330977 534768913 536599904 536867089 532365675 532676195 536862761 536871120 536870413 603994438 536764403 535801172 ...
result:
wrong answer 12th numbers differ - expected: '537003864', found: '536709016'