QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153347 | #6521. Swapping Operation | training4usaco | WA | 59ms | 20608kb | C++17 | 2.3kb | 2023-08-29 22:47:01 | 2023-08-29 22:47:01 |
Judging History
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) {
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);
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);
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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 20560kb
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: 59ms
memory: 20608kb
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'