제출 #1308003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308003		biank	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	28 ms	11184 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(n);
    forn(i, n) if (s[i] > 0) where[s[i] - 1].pb(i);
    forn(i, n) reverse(all(where[i]));
    vi perm(n);
    int pos = 0;
    forn(i, n) if (s[i] < 0) {
        perm[i] = pos++;
        int j = where[-s[i] - 1].back();
        where[-s[i] - 1].pop_back();
        perm[j] = 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: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15