Submission #1264765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264765		eduardmm	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	328 KiB

shoes

#include <vector>
#include <bits/stdc++.h>

long long count_swaps(std::vector<int> S){

    int n = S.size();

    std::vector<std::vector<int>> ind(n + 1);
    long long ans = 0;

    for (int i = 0; i < n; ++i){
        int u = S[i];

        if (ind[abs(u)].size() == 0){
            ind[abs(u)].push_back(i);
            continue;
        }
        
        int v = ind[abs(u)].back();
        v = S[v];
        if (std::signbit(v) != std::signbit(u)){
            ans += i - ind[abs(u)].back() - 1;
            if (v > 0 && u < 0) ans++;

            ind[abs(u)].pop_back();
        }
    }

    return ans;
}

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