QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122009 | #6521. Swapping Operation | Sorting | WA | 0ms | 13816kb | C++20 | 5.2kb | 2023-07-09 04:02:38 | 2023-07-09 04:02:39 |
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] = a[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();
if(n <= 100){
int ans = do_alg();
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
swap(a[i], a[j]);
ans = max(ans, do_alg());
swap(a[i], a[j]);
}
}
cout << ans << "\n";
return;
}
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());
// answers.push_back(do_alg());
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();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13816kb
input:
3 6 6 5 4 3 5 6 6 1 2 1 1 2 2 5 1 1 2 2 2
output:
0 0 0
result:
wrong answer 1st numbers differ - expected: '7', found: '0'