| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 411383 | ollel | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll ans = 0;
int n;
vi shoes;
int f(int x, int m) {
return (x > 0) ? x : m - 1 + x;
}
void rem() {
int pairs = n/2;
rep(pair, 0, pairs) {
vi dist(pairs, 0);
rep(i,0,n) dist[shoes[i]] += i;
int bd = 1e9, p;
rep(i, 0, pairs) {
if (dist[i] < bd) {bd = dist[i]; p = i;}
}
ans += bd - 1;
rep(i, 0, n-1) if (shoes[i] == p) swap(shoes[i], shoes[i + 1]);
rep(i, 0, n-1) if (shoes[i] == p) swap(shoes[i], shoes[i + 1]);
}
}
int main()
{
cin >> n; shoes.resize(n); rep(i,0,n) cin >> shoes[i];
rep(i,0,n) shoes[i] = -shoes[i];
vvi exists(2*n + 5);
rep(i,0,n) exists[f(shoes[i], 2*n+5)].pb(i);
int real = 0;
rep(i,1,n+1) {
rep(j, 0, exists[i].size()) {
int a = exists[i][j], b = exists[f(-i, 2*n+5)][j];
if (a > b) ans++;
shoes[a] = shoes[b] = real;
real++;
}
}
rem();
cout << ans << endl;
}