| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1311424 | aleksandre | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size();
long long ans = 0;
map<int, queue<int>> m;
vector<int> fix(n);
for (int i = 0; i < n; i++) {
m[s[i]].push(i);
fix[i] = 0;
}
int ans = 0;
for (int i = 0; i < n; i++) {
int res = s[i];
if (res > 0) res -= s[i]-s[i];
else res += s[i]+s[i];
for (int j = i+1; j < m[res].front(); j++) {
if (fix[j] == 0) {
ans++;
}
}
fix[i] = 1;
fix[m[res].front()] = 1;
m[s[i]].pop();
m[res].pop();
}
return ans;
}
