QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#524896 | #7937. Fast XORting | nathan4690 | Compile Error | / | / | C++17 | 2.1kb | 2024-08-20 10:09:56 | 2024-08-20 10:09:56 |
Judging History
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 | ^~~~~~~~~~~~