QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153349#6521. Swapping Operationtraining4usacoWA 54ms20808kbC++172.3kb2023-08-29 22:53:352023-08-29 22:53:35

Judging History

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

  • [2023-08-29 22:53:35]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:20808kb
  • [2023-08-29 22:53:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int LOG = 22;
const int MAXN = 1e5 + 5;

int n;
int a[MAXN];
int st[LOG][MAXN];
int lg[MAXN];
vector<int> important;
map<int, vector<int>> bf;	// bruteforce

int qry(int l, int r) {
	if(l > r) return (1 << (LOG + 1)) - 1;

	int lgg = lg[r - l + 1];
	return st[lgg][l] & st[lgg][r - (1 << lgg) + 1];
}

void solve() {
	cin >> n;

	for(int i = 0; i < LOG; ++i) {
		for(int j = 0; j <= n; ++j) {
			a[j] = 0; st[i][j] = 0;
		}
	}

	for(int i = 1; i <= n; ++i) {
		cin >> a[i]; st[0][i] = a[i];
	}

	for(int h = 1; h < LOG; ++h) {
		for(int i = 1; i <= (n - (1 << h) + 1); ++i) {
			st[h][i] = st[h - 1][i] & st[h - 1][i + (1 << (h - 1))];
		}
	}

	vector<int> pref, suff;
	int mask = (1 << LOG) - 1;
	for(int i = 1; i <= n; ++i) {
		if(mask != (mask & a[i])) pref.push_back(i);
		mask = mask & a[i];
	}

	mask = (1 << LOG) - 1;
	for(int i = n; i >= 1; --i) {
		if(mask != (mask & a[i])) suff.push_back(i);
		mask = mask & a[i];
	}

	int ans = 0;
	for(int k = 1; k < n; ++k) {
		ans = max(ans, qry(1, k) + qry(k + 1, n));
	}

	for(int k = 1; k < n; ++k) {
		for(auto x : pref) {
			if(x > k) continue;

			for(auto y : suff) {
				if(y <= k) continue;

				ans = max(ans, (qry(1, x - 1) & qry(x + 1, k) & a[y]) + (qry(k + 1, y - 1) & qry(y + 1, n) & a[x]));
			}
		}
	}

	bf.clear();
	for(int k = 1; k < n; ++k) {
		for(auto x : pref) {
			if(x > k) continue;

			int prefv = qry(1, x - 1) & qry(x + 1, k);
			if(bf.count(prefv) == 0) {
				vector<int> vals(n + 2, 0);

				for(int i = n; i >= 1; --i) {
					vals[i] = max(vals[i + 1], a[i] & prefv);
				}

				bf[prefv] = vals;
			}
			ans = max(ans, bf[prefv][k + 1] + (qry(k + 1, n) & a[x]));
		}
	}

	bf.clear();
	for(int k = 1; k < n; ++k) {
		for(auto y : suff) {
			if(y <= k) continue;

			int suffv = qry(k + 1, y - 1) & qry(y + 1, n);
			if(bf.count(suffv) == 0) {
				vector<int> vals(n + 2, 0);

				for(int i = 1; i <= n; ++i) {
					vals[i] = max(vals[i - 1], a[i] & suffv);
				}

				bf[suffv] = vals;
			}
			ans = max(ans, bf[suffv][k] + (qry(1, k) & a[y]));
		}
	}

    cout << ans << '\n';
}

signed main() {
	lg[1] = 0;
	for(int i = 2; i <= MAXN; ++i) lg[i] = lg[i / 2] + 1;

	int t; cin >> t;
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 20768kb

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: -100
Wrong Answer
time: 54ms
memory: 20808kb

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:

803046221
216853540
431591996
691543221
906186590
585304767
538989750
706192264
389841717
510167848
474633170
308054317
361149101
917264022
863440694
368081494
301188372
142231104
729655322
671698569
857478209
662348695
924124296
451873533
687355066
726232064
766486586
312704375
367792663
599277840
...

result:

wrong answer 1st numbers differ - expected: '999397418', found: '803046221'