# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1056717 | jamesbamber | Arranging Shoes (IOI19_shoes) | C++17 | 204 ms | 77592 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;
long long count_swaps(std::vector<int> s) {
int n = s.size()/2;
vector<int> numid(2*n);
map<int, queue<int>> nums;
int ct = 0;
for(int i=0; i<2*n; i++){
if(nums.count(s[i]) and nums[s[i]].size() != 0){
numid[i] = nums[s[i]].front();
nums[s[i]].pop();
}
else{
numid[i] = ct;
nums[-s[i]].push(ct);
ct++;
}
}
vector<int> perm(2*n);
for(int i=0; i<2*n; i++){
perm[i] = (s[i] > 0)?2*numid[i]+1:2*numid[i];
}
vector<int> fw(2*n+1);
auto add = [&](int i, int x){
for(; i<fw.size(); i+= i&-i) fw[i] += x;
};
auto query = [&](int i){
int ans = 0;
for(; i>0; i -= i&-i) ans += fw[i];
return ans;
};
long long ans = 0;
for(int i=0; i<2*n; i++){
ans += i - query(perm[i]);
add(perm[i]+1, 1);
}
return ans;
}
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... |