| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1047327 | vjudge1 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
struct Fenwick {
vector<int> data;
int n;
void reset(int s) {
n = s;
data.assign(n + 3, 0);
}
void update(int ind, int val) {
ind++;
while(ind <= n) {
data[ind] += val;
ind += ind & (-ind);
}
}
int getSum(int ind) {
ind++;
int ret = 0;
while(ind > 0) {
ret += data[ind];
ind -= ind & (-ind);
}
return ret;
}
int query(int l, int r) {
return getSum(r) - (l > 0 ? getSum(l - 1) : 0);
}
};
long long count_swaps(std::vector<int> s) {
int n = (int)s.size() / 2;
vector<vector<int> > sn(n + 2, vector<int>()), sp(n + 2, vector<int>());
vector<array<int, 2> > pr;
for(int i = 0; i < 2*n; i++) {
if(s[i] < 0) {
sn[abs(s[i])].pb(i);
}
else {
sp[abs(s[i])].pb(i);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < sn[i].size(); j++) {
pr.pb({sn[i][j], sp[i][j]});
}
}
sort(all(pr), [&](array<int, 2> x, array<int, 2> y) {
return x[0] + x[1] < y[0] + y[1];
});
Fenwick fn;
fn.reset(2*n + 3);
int ans = 0;
int cur = 0;
for(int i = 0; i < n; i++) {
for(auto c : pr[i]) {
s[cur] = c;
cur++;
}
}
for(int i = 0; i < 2*n; i++) {
// cout << "i:" << s[i] << "\n";
ans += fn.query(s[i] + 1, 2*n);
fn.update(s[i], 1);
}
return ans;
}