# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
295731 | tzero | Arranging Shoes (IOI19_shoes) | C++14 | 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 <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <cassert>
#include <cstring>
using namespace std;
using ll = long long;
const int maxn = (int)1e5 + 7;
int t[8 * maxn], lz[8 * maxn];
int n;
void update(int v, int tl, int tr, int l, int r) {
if(tl > r || tr < l) {
return;
} else if(tl >= l && tr <= r) {
lz[v]++;
} else {
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r);
update(2 * v + 1, tm + 1, tr, l, r);
}
}
int query(int v, int tl, int tr, int i) {
if(tl > i || tr < i) {
return -1;
}
if(lz[v] > 0) {
t[v] += lz[v];
if(tl != tr) {
lz[2 * v] += lz[v];
lz[2 * v + 1] += lz[v];
}
lz[v] = 0;
}
if(tl == tr) {
return t[v];
} else {
int tm = (tl + tr) / 2;
int ans = query(2 * v, tl, tm, i);
if(ans != -1) return ans;
ans = query(2 * v + 1, tm + 1, tr, i);
return ans;
}
}
ll count_swaps(vector<int> s) {
n = (int)s.size();
bool same_size = true;
for(int i = 0; i < n; i++) {
if(i > 0 && abs(s[i]) != abs(s[i - 1])) same_size = false;
}
if(same_size) {
ll move_left = 0, move_right = 0;
int found_left = 0, found_right = 0;
for(int i = 0; i < n; i++) {
if(s[i] < 0) {
int pos = found_left * 2;
move_left += abs(i - pos);
found_left++;
} else {
int pos = found_right * 2 + 1;
move_right += abs(i - pos);
found_right++;
}
}
return min(move_left, move_right);
}
memset(t, 0, sizeof(t));
memset(lz, 0, sizeof(lz));
ll ans = 0;
int half = n / 2;
vector<vector<int> > positions(n + 1);
vector<bool> taken(n, false);
for(int i = 0; i < n; i++) {
positions[s[i] + half].push_back(i);
}
int real_idx = n - 1;
for(int pos_right = n - 1; pos_right >= 1; pos_right -= 2) {
while(taken[real_idx]) real_idx--;
int real_idx = *prev(indexes_left.end());
int idx_left = positions[-s[real_idx] + half].back();
int pos_left = idx_left - query(1, 0, n - 1, idx_left);
assert(s[real_idx] == s[idx_left] == 0);
ans += pos_right - pos_left;
if(s[real_idx] > 0) ans--;
update(1, 0, n - 1, idx_left, n - 1);
positions[s[real_idx] + half].pop_back();
positions[-s[real_idx] + half].pop_back();
taken[real_idx] = true;
taken[idx_left] = true;
}
return ans;
}
// TOTAL: 100 puntos
int _main() {
int n;
scanf("%d", &n);
vector<int> _s(2 * n);
for(int i = 0; i < 2 * n; i++) {
scanf("%d", &_s[i]);
}
printf("%lld\n", count_swaps(_s));
return 0;
}