| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 413975 | asfd221 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define INF (ll)(2e9)
#define MD (998244353)
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;
using ll = long long;
using cd = complex<double>;
using ul = unsigned long;
void f_io () { ios_base :: sync_with_stdio (false); cin.tie (nullptr);
cout.tie (nullptr);
}
const ll MAX = 2e5 + 5, MOD = 998244353, M = 3e6;
ll gc (ll a, ll b) {
if (!a || !b) {
return max (a, b);
}
ll r = a % b;
while (r) {
a = b;
b = r;
r = a % b;
}
return b;
}
ll mult (ll a, ll b) {
return ((a % MOD) * 1LL * (b % MOD)) % MOD;
}
ll add (ll a, ll b) {
b = (b % MOD + MOD) % MOD;
return (a + b) % MOD;
}
ll pw (ll a, ll b) {
if (b < 0) {
return 1;
}
ll r = 1;
while (b) {
if (b & 1) {
r = mult (a, r);
}
b >>= 1;
a = mult (a, a);
}
return r;
}
int f[MAX];
void up (int x, int v) {
x++;
for (int i = x; i < MAX; i += i & (-i)) {
f[i] += v;
}
}
ll an (int x) {
ll s = 0;
x++;
for (int i = x; i; i -= i & (-i)) {
s += f[i];
}
return s;
}
ll inv (vector<int> v) {
for (ll i = 0; i < (int)v.size () + 10; i++) {
f[i] = 0;
}
ll a =0;
for (ll i = v.size () - 1; i >= 0; i--) {
a += an (v[i]);
up (v[i] + 1, 1);
}
return a;
}
ll count_swaps (vector<int> ve) {
int n = ve.size ();
vector<int> vv (n), v2 (n);
int cc = 0, c[n + 1] = {}, c2 = 1, d[n + 1] = {};
vector<int> id[n + 1], i2[n + 1];
for (int i = 0; i < n; i++) {
if (ve[i] < 0) {
vv[i] = cc;
id[-ve[i]].pb (cc);
cc += 2;
}
else {
v2[i] = c2;
i2[ve[i]].pb (c2);
c2 += 2;
}
}
for (int i = 0; i < n; i++) {
if (ve[i] > 0) {
vv[i] = id[ve[i]][c[ve[i]]++] + 1;
}
else {
vv[i] = i2[-ve[i]][d[-ve[i]]++] - 1;
}
}
return min (inv (vv), inv (v2));
}