Submission #347196

#	Time	Username	Problem	Language	Result	Execution time	Memory
347196		ljuba	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	91 ms	13544 KiB

shoes

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

typedef long long ll;

using namespace std;

const int mxN = 2e5;

ll ft[mxN+1];

void update(int i, ll x) {
    for(; i <= mxN; i += i&-i) {
        ft[i] += x;
    }
}

ll query(int i) {
    ll r = 0;
    for(; i; i -= i&-i) {
        r += ft[i];
    }
    return r;
}

ll count_swaps(vector<int> s) {
    int n = (int)s.size();

    vector<pair<int, int>> mesta[n+1];

    for(int i = 0; i < n; ++i) {
        mesta[abs(s[i])].push_back({s[i], i});
    }

    for(int i = 1; i <= n; ++i) {
        sort(mesta[i].begin(), mesta[i].end());
    }

    ll ans = 0;

    vector<pair<int, int>> parovi;

    for(int i = 1; i <= n/2; ++i) {
        for(int j = 0; j < (int)mesta[i].size()/2; ++j) {
            int l = mesta[i][j].second;
            int r = mesta[i][j+mesta[i].size()/2].second;
            if(l > r) {
                ++ans;
                swap(l, r);
            }
            parovi.push_back({l+1, r+1});
        }
    }

    sort(parovi.begin(), parovi.end());

    for(int i = 1; i <= n; ++i)
        update(i, 1);

    for(auto z : parovi) {
        ans += query(z.second-1) - query(z.first);
        update(z.first, -1);
        update(z.second, -1);
    }

    return ans;
}

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