Submission #1012995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012995		aufan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	174 ms	27624 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

long long count_swaps(vector<int> s) {
    int n = s.size();
    long long ans = 0;
    int p = 0;
    vector<int> fin(n);
    map<int, vector<int>> id;
    for (int i = 0; i < n; i++) {
        id[s[i]].push_back(i);
    }
    vector<pair<int, int>> br;
    for (int i = 1; i <= n/2; i++) {
        int sz = id[i].size();
        for (int j = 0; j < sz; j++) {
            int lf = min(id[-i][j], id[i][j]);
            int rg = max(id[-i][j], id[i][j]);
            br.push_back(make_pair(lf, rg));
        }
    }
    /*
    1 1 -1 -1
    0 1 2 3
    {0, 2}, {1, 3}
    */
    sort(br.begin(), br.end());
    for (int i = 0; i < n/2; i++) {
        fin[2*i] = br[i].first;
        fin[2*i + 1] = br[i].second;
        if (s[fin[2*i]] > 0) swap(fin[2*i], fin[2*i + 1]);
    }
    /*
    0 1 2 3 4 5
    0 2 1 4 3 5
    0 2 1 4 5 3
    */
    vector<int> fen(n+1, 0);
    auto add = [&](int x) {
        for (;x<=n;x+=x&-x) fen[x]++;
    };
    auto get = [&](int x) {
        int res = 0;
        for (;x>0;x-=x&-x) res+=fen[x];
        return res;
    };
    for (int i = 0; i < n; i++) {
        int pos = fin[i] + 1 + (get(n) - get(fin[i]+1));
        ans += pos - i - 1;
        add(fin[i]+1);
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:9:9: warning: unused variable 'p' [-Wunused-variable]
    9 |     int p = 0;
      |         ^

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