QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304805#6521. Swapping Operationucup-team2894#WA 87ms5928kbC++202.8kb2024-01-14 03:31:522024-01-14 03:31:53

Judging History

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

  • [2024-01-14 03:31:53]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:5928kb
  • [2024-01-14 03:31:52]
  • 提交

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'