QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#786730 | #7937. Fast XORting | ucup-team3646 | WA | 40ms | 6204kb | C++20 | 1.8kb | 2024-11-26 23:07:59 | 2024-11-26 23:08:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, l, r) for (ll i = l; i < r; i++)
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;
bool chmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, const auto &b) { return a < b ? a = b, 1 : 0; }
struct IOSetup {
IOSetup() {
cin.tie(0);
ios::sync_with_stdio(0);
}
} iosetup;
template <class T>
void print(vector<T> a) {
for (auto x : a) cerr << x << ' ';
cout << endl;
}
void print(auto x) { cout << x << endl; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
cout << head << ' ';
print(forward<Tail>(tail)...);
}
struct BIT {
ll n;
vector<ll> data;
BIT() = default;
BIT(ll n) : n(n), data(n + 1, 0) { }
// a_x += val;
void add(ll x, ll val) {
x++;
for ( ; x <= n; x += x & -x) data[x] += val;
return;
}
// sum of a[0, x)
ll sum(ll x) {
ll ret = 0;
for ( ; x > 0; x -= x & -x) ret += data[x];
return ret;
}
// sum of a[lx, rx)
ll sum(ll lx, ll rx) {
return sum(rx) - sum(lx);
}
};
int main() {
int n;
cin>>n;
vi a(n);
rep(i,n)cin>>a[i];
ll inv=0;
BIT bit(n);
rep(i,n){
inv+=bit.sum(a[i],n);
bit.add(a[i],1);
}
ll ans2=inv+1;
for(int i=1;i<n;i*=2){
ll now=0,nxt=0;
for(int l=0;l<n;l+=2*i){
ll c0=0,c1=0;
rep2(j,l,l+2*i){
if((a[j]&i)==0){
now+=c1;
c0++;
}
else{
nxt+=c0;
c1++;
}
}
}
if(now>nxt){
ans2+=-now+nxt;
}
}
cout<<min(inv,ans2)<<endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
8 0 1 3 2 5 4 7 6
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
8 2 0 1 3 4 5 6 7
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 40ms
memory: 6204kb
input:
262144 47482 131703 90418 122675 166494 247529 196154 16950 66501 50357 246808 25929 10418 50538 26955 151884 63776 58023 20073 26544 74785 44064 41836 148543 87920 54172 3270 131495 130960 112122 167229 215767 77499 195004 21391 11039 168999 256346 109690 180904 172679 157200 78594 201857 52784 147...
output:
17142422187
result:
wrong answer 1st numbers differ - expected: '17137565829', found: '17142422187'