QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524896#7937. Fast XORtingnathan4690Compile Error//C++172.1kb2024-08-20 10:09:562024-08-20 10:09:56

Judging History

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

  • [2024-08-20 10:09:56]
  • 评测
  • [2024-08-20 10:09:56]
  • 提交

answer

// Fast XORting
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

struct FenwickTree{
    ll n;
    vector<ll> bit;
    FenwickTree(ll n): n(n), bit(n+1, 0ll){};
    void update(ll idx, ll v){for(;idx<=n;idx+=idx&-idx) bit[idx] += v;}
    ll getSum(ll idx){
        ll res = 0;
        for(;idx>0;idx-=(idx&-idx)) res += bit[idx];
        return res;
    }
};

ll n,a[maxn],ans;
vector<ll> all;
bool flag;

ll solve(const vector<ll> &v, ll bit, ll val){
    ll ans = 0;
    ll c0 = 0, a0 = 0, c1 = 0, a1 = 0;
    vector<ll> v0, v1;
    for(ll i=v.size()-1;i>=0;i--){
        ll item = v[i];
        if(((item & (1 << bit)) != val)) {
            v1.push_back(item);
            c1++;
            a1 += c0;
        }else {
            v0.push_back(item);
            c0++;
        }
    }
    reverse(v0.begin(), v0.end());
    reverse(v1.begin(), v1.end());
    // cout << bit << ' ' << a0 << ' ' << a1;el;
    ans += a1;
    if(bit){
        ll vv0 = solve(v0, bit-1, 0) + solve(v1, bit-1, 0);
        ll vv1 = solve(v0, bit-1, 1) + solve(v1, bit-1, 1);
        // if(vv1 > vv0) flag = false;
        ans += min(vv0, vv1);
    }
    return ans;
}

FenwickTree fen(maxn);

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n;
    f1(i,n) {
        cin >> a[i];
        // cout << bitset<3>(a[i]).to_string();el;
    }
    ll preans = 0;
    for(ll i=n;i>=1;i--){
        preans +=fen.getSum(a[i]);
        fen.update(a[i] + 1, 1);
    }
    f1(i,n) all.push_back(a[i]);
    flag = true;
    ll vv0 = solve(all, __lg(n) - 1, 0);
    ll vv1 = solve(all, __lg(n) - 1, 1);
    // if(vv1 > vv0) flag = false;
    cout << min(min(vv0, vv1) + 1, preans);
    return 0;
}

详细

answer.code: In function ‘int main()’:
answer.code:63:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:64:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~