# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
143197 | mlyean00 | Arranging Shoes (IOI19_shoes) | C++17 | 1012 ms | 153452 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 <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
int sgn(int x) {
if (x == 0) return 0;
return x > 0 ? 1 : -1;
}
ll count_inversions(vector<int>& v, int l, int r) {
if (r - l == 1) return 0;
int mid = (l + r) / 2;
ll ans = count_inversions(v, l, mid) + count_inversions(v, mid, r);
int l_ptr = l, r_ptr = mid;
vector<int> m;
m.reserve(r - l);
while (l_ptr < mid || r_ptr < r) {
if (l_ptr == mid) {
m.push_back(v[r_ptr++]);
} else if (r_ptr == r) {
ans += r_ptr - mid;
m.push_back(v[l_ptr++]);
} else if (v[l_ptr] <= v[r_ptr]) {
ans += r_ptr - mid;
m.push_back(v[l_ptr++]);
} else {
m.push_back(v[r_ptr++]);
}
}
copy(m.begin(), m.end(), v.begin() + l);
return ans;
}
ll count_swaps(vector<int> s) {
int n = s.size() / 2;
vector<int> t;
map<int, int> cnt;
for (int i = 0; i < 2 * n; ++i) {
int sz = abs(s[i]);
if (cnt[sz] == 0 || sgn(s[i]) == sgn(cnt[sz])) {
t.push_back(-sz);
t.push_back(sz);
}
cnt[sz] += sgn(s[i]);
}
assert(t.size() == 2 * n);
map<int, stack<int>> m;
for (int i = 2 * n - 1; i >= 0; --i) {
m[s[i]].push(i);
}
vector<int> perm(2 * n);
for (int i = 0; i < 2 * n; ++i) {
perm[i] = m[t[i]].top();
m[t[i]].pop();
}
return count_inversions(perm, 0, 2 * n);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |