제출 #1308007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308007		biank	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	43 ms	19124 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define sum(x) accumulate(all(x), 0LL)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

struct FTree {
    int n;
    vi ft;
    FTree(int _n) : n(_n + 9), ft(n, 0) {}
    void add(int p) {
        for (++p; p < n; p += p & -p) ft[p]++;
    }
    int get(int p) {
        int s = 0;
        for (; p > 0; p -= p & -p) s += ft[p];
        return s;
    }
};

ll count_swaps(vi s) {
    const int n = sz(s);
    vector<vi> where(2 * n + 1);
    forn(i, n) where[s[i] + n].pb(i);
    forn(i, 2 * n + 1) reverse(all(where[i]));
    vi perm(n, -1);
    int pos = 0;
    auto clear = [&](vi &p) {
        while (perm[p.back()] != -1) p.pop_back();
    };
    forn(i, n) if (perm[i] == -1) {
        int a = i, x = s[i];
        clear(where[-x + n]);
        int b = where[-x + n].back();
        if (x > 0) swap(a, b);
        perm[a] = pos++;
        perm[b] = pos++;
    }
    FTree ft(n);
    ll ret = 0;
    dforn(i, n) {
        ret += ft.get(perm[i]);
        ft.add(perm[i]);
    }
    return ret;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15