QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304805 | #6521. Swapping Operation | ucup-team2894# | WA | 87ms | 5928kb | C++20 | 2.8kb | 2024-01-14 03:31:52 | 2024-01-14 03:31:53 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using pll = pair<ll,ll>;
using vi = vector<int>;
#define fr first
#define sc second
mt19937_64 rnd (220);
using ld = long double;
#define all(x) (x).begin(), (x).end()
const int maxn = 1e5+10, inf = 1e9+100;
const ll linf = 4e18+100;
const int mod = 998244353;
int a[maxn];
int psa[maxn][30];
vi inds[30],zinds[30];
int tot[30];
void solve () {
int n;
cin >> n;
// n=1e5;
memset(tot,0,sizeof(tot));
for(int i=0;i<30;i++)inds[i].clear(),zinds[i].clear();
for(int i=0;i<30;i++)for(int j=0;j<=n;j++)psa[j][i]=0;
// for(int i=1;i<=n;i++)a[i]=(1<<29)-1;
for(int i=1;i<=n;i++)cin >> a[i];
vi rel;
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++){
if((a[i]>>j)&1){
tot[j]++;
psa[i][j]++;
inds[j].push_back(i);
}
else zinds[j].push_back(i);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++)psa[i][j]+=psa[i-1][j];
}
for(int j=0;j<30;j++){
for(int i=2;i<=n;i++){
if(psa[i][j]==i-1&&psa[i-1][j]==i-1){
rel.push_back(i-1);
if(i<n)rel.push_back(i);
}
if(psa[i][j]==i-2&&psa[i-1][j]==i-2){
rel.push_back(i-1);
if(i>2)rel.push_back(i-2);
}
}
for(int i=n-1;i>=1;i--){
if(tot[j]-psa[i-1][j]==n-i&&tot[j]-psa[i][j]==n-i){
rel.push_back(i);
if(i>1)rel.push_back(i-1);
}
if(tot[j]-psa[i-1][j]==n-i-1&&tot[j]-psa[i][j]==n-i-1){
rel.push_back(i);
if(i<n-1)rel.push_back(i+1);
}
}
}
sort(all(rel));
rel.erase(unique(all(rel)),rel.end());
if(rel.size()==0)rel.push_back(0);
int ans = 0;
for(int co : rel) {
int tar = 0;
vi cands;
// cerr << co << endl;
for(int j=29;j>=0;j--){
if(tot[j]>=n-1)continue;
if(psa[co][j]==co-1&&psa[co][j]!=tot[j]){
tar=zinds[j][0];
for(int i : inds[j]) if(i>co){
cands.push_back(i);
}
break;
}
if(tot[j]-psa[co][j]==n-co-1&&psa[co][j]!=0){
tar=zinds[j].back();
for(int i : inds[j]) if(i<=co){
cands.push_back(i);
}
// if(co==5){
// cerr << j << endl;
// cerr << tar << endl;
// for(int x : cands) cerr << x << endl;}
break;
}
}
cands.push_back(tar);
for(int i : cands) {
int cans = 0;
for(int j=29;j>=0;j--){
int rp = psa[co][j];
if(tar!=i){
rp += (tar<=co?-1:1)*(((a[tar]>>j)&1)-((a[i]>>j)&1));
}
if(rp==co)cans+=1<<j;
if(tot[j]-rp==n-co)cans+=1<<j;
}
ans=max(ans,cans);
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout<<fixed;
cout.precision(20);
int tc;
cin >> tc;
// tc = 1;
while(tc--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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: 85ms
memory: 5928kb
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: -100
Wrong Answer
time: 87ms
memory: 3884kb
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:
wrong answer 222nd numbers differ - expected: '998210353', found: '992657346'