이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pi pair<int,int>
long long count_swaps(vector<int> s) {
ll ans = 1e18;
int n = s.size();
vector<pi> lefts(n/2);
int cntleft = 0;
vector<pair<int, pi>> sortlefts(n/2);
vector<queue<int>> rightinds(n);
for(int i =0; i<n ;i++){
if(s[i] > 0){
rightinds[s[i]].push(i);
}
}
for(int i =0; i<n; i++){
if(s[i] < 0){
int firstright = rightinds[-s[i]].front();
rightinds[-s[i]].pop();
lefts[cntleft++] = {i, firstright};
sortlefts[cntleft - 1] = {i+firstright, {i, firstright}};
}
}
sort(sortlefts.begin(), sortlefts.end());
for(int i =0; i<n/2; i++){
lefts[i] = sortlefts[i].second;
}
ll posans = 0;
vector<int> inds(n);
for(int i =0; i<n ;i++) inds[i] = i;
//for(int i =0; i<n/ 2; i++) cout << lefts[i]<<", "; cout <<endl;
int l = 0;
for(pi shoe : lefts){
//get first availabe
int leftind = shoe.first;
int rightind = shoe.second;
//cout <<endl;
ll dist1 = abs(inds[leftind] - 2 * l);
for(int k = 0; k<n ;k++){
if(inds[k] >= 2 * l && inds[k] < inds[leftind])
inds[k]++;
}
ll dist2 = abs(inds[rightind] -( 2 * l + 1));
for(int k =0;k<n; k++){
if(inds[k] >=2* l + 1 and inds[k] < inds[rightind])
inds[k]++;
}
//cout << inds[lefts[l]]<<", "<<inds[firstright]<<": ";
//cout << lefts[l]<<", "<<firstright<<": "<<dist1<<", "<<dist2<<endl;
posans += dist1 + dist2;
l++;
}
ans = min(ans, posans);
//cout << posans<<endl<<endl;
return ans;
}
/***********/
# | 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... |