QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122009#6521. Swapping OperationSortingWA 0ms13816kbC++205.2kb2023-07-09 04:02:382023-07-09 04:02:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-09 04:02:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13816kb
  • [2023-07-09 04:02:38]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'