Submission #521603

#	Time	Username	Problem	Language	Result	Execution time	Memory
521603		tabr	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	288 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

long long count_swaps(vector<int> s) {
    int n = (int) s.size();
    long long ans = 0;
    {
        vector<vector<int>> cnt(2 * n + 1);
        for (int i = 0; i < n; i++) {
            cnt[s[i] + n].emplace_back(i);
        }
        int c = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < (int) cnt[n + i].size(); j++) {
                s[cnt[n + i][j]] = c;
                s[cnt[n - i][j]] = c;
                if (cnt[n + i][j] < cnt[n - i][j]) {
                    ans++;
                }
                c++;
            }
        }
    }
    debug(ans, s);
    
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << count_swaps({2, 1, -1, -2}) << '\n';
    cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';
    cout << count_swaps({-1, 2, 1, 1, -2, -1}) << '\n';
    return 0;
}
#endif

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