이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 5;
int n;
map<int, int> mp[2];
long count_swaps(vector<int> s) {
n = (int)s.size();
long ans = 0;
for(int i = 0; i < n; i += 2) {
if(s[i] == -s[i + 1]) {
if(s[i] > 0) swap(s[i], s[i + 1]), ++ans;
continue;
}
mp[0].clear(), mp[1].clear();
for(int j = n - 1; j >= i; j--) {
if(s[j] < 0) mp[0][abs(s[j])] = j;
else mp[1][abs(s[j])] = j;
}
int id = -1, cnt = 1e9;
for(pii p : mp[0]) {
int a = p.y, b = mp[1][p.x];
if(a - i + b - i - 1 + (a > b) < cnt) {
cnt = a - i + b - i - 1 + (a > b);
id = p.x;
}
}
ans += cnt;
int l = mp[0][id], r = mp[1][id];
if(l > r) ++r;
while(l != i) swap(s[l - 1], s[l]), --l;
while(r != i + 1) swap(s[r - 1], s[r]), --r;
}
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... |