Submission #1313001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313001		shirokito	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	43 ms	14244 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

#define all(a) (a).begin(), (a).end()

using ll = long long;

const int N = 2e5 + 24;

vector<int> pos[N];
int n, t[N], del[N];

void update(int i, int v) {
    for (; i < N; i += i & (-i)) t[i] += v;
}

int get(int i) {
    int res = 0;
    for (; i > 0; i -= i & (-i)) res += t[i];
    return res;
}

ll count_swaps(vector<int> S) {
    n = S.size() / 2;

    for (int &x: S) {
        if (x < 0) x = -x + n;
    }

    for (int i = n * 2; i >= 1; i--) {
        pos[S[i - 1]].push_back(i);
        update(i, 1);
    }

    ll res = 0;

    for (int i = 0; i < 2 * n; i++) {
        if (del[i]) continue;

        int u = S[i], v = S[i] + (S[i] <= n ? n : -n);
        
        int pos_u = pos[u].back(); pos[u].pop_back();
        int pos_v = pos[v].back(); pos[v].pop_back();

        int x = get(pos_u), y = get(pos_v);

        res += abs(x - y) - 1;
        if (u <= n) res++;

        update(pos_u, -1); del[pos_u - 1] = 1;
        update(pos_v, -1); del[pos_v - 1] = 1;
    }

    return res;
}

#ifdef LOCAL
void solve() {
    int n; cin >> n;
    vector<int> a(2 * n); for (int &x: a) cin >> x;

    cout << count_swaps(a) << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}
#endif

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