# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
399049 | mshandilya | Arranging Shoes (IOI19_shoes) | C++14 | 1 ms | 332 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) {
long long N = s.size(), left_pair = 0, right_pair = 0, sort_inversions = 0, total_inversions = 0;
std::vector<int> position(N);
std::vector<queue<int>> compensated_inversions(N+1);
for(int i = 2*N-1; i>=0; i--) {
if(s[i]<0) {
compensated_inversions[abs(s[i])].push(left_pair);
left_pair++;
position[s[i]] = N-left_pair;
}
else if(!compensated_inversions[s[i]].empty()) {
total_inversions += left_pair - compensated_inversions[s[i]].front();
compensated_inversions[s[i]].pop();
}
}
for(int i = 0; i<2*N-1; i++) {
if(s[i]>0) {
int cpos = position[s[i]];
for(int j = i+1; j<2*N-1; j++)
if(s[j]>0 && position[s[j]]<cpos)
sort_inversions++;
}
}
return (total_inversions+sort_inversions);
}
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... |