QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121999 | #6521. Swapping Operation | Sorting | RE | 1ms | 11652kb | C++20 | 4.8kb | 2023-07-09 02:29:17 | 2023-07-09 02:29:19 |
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] = 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 = 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();
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());
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();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 11652kb
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
Runtime Error
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...