Submission #577900

#	Time	Username	Problem	Language	Result	Execution time	Memory
577900		mi_ni_	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	469 ms	546612 KiB

shoes

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

long long merge_util(vector<int> &arr, int l, int r) {
    int mid = (l+r)/2;
    long long cnt = 0;
    int it1 = l, it2 = mid+1;
    while(it2 <= r) {
        while(it1 <= mid && arr[it1] < arr[it2]) it1++;
        cnt += (mid+1-it1);
        it2++;
    }
    vector<int> temp(r-l+1);
    merge(arr.begin()+l, arr.begin()+mid+1, arr.begin()+mid+1, arr.begin()+r+1, temp.begin());
    copy(temp.begin(), temp.end(), arr.begin()+l);
    return cnt;
}
 
long long find_inversions(vector<int> &arr, int l, int r) {
    if(r <= l) return 0ll;
    int mid = (l+r)/2;
    long long ans = find_inversions(arr, l, mid) + find_inversions(arr, mid+1, r);
    ans += merge_util(arr, l, r);
    return ans;
}
 
long long find_swaps(vector<int> from, vector<int> to) {
    assert(from.size() == to.size());
    int n = from.size();
    vector<stack<int>> s(2*n + 5);
    for(int ind = n-1; ind >= 0; ind--) s[to[ind]+n].push(ind);
    vector<int> pos;
    for(auto i:from) {
        pos.push_back(s[i+n].top());
        s[i+n].pop();
    }
    return find_inversions(pos, 0, n-1);
}

long long count_swaps(vector<int> S) {
    int n = S.size();
    vector<int> to;
    vector<stack<int>> m(2*n + 5);
    for(int i = n-1; i>=0; i--) m[S[i]+n].push(i);
    vector<bool> done(n, 0);
    for(int i=0; i<n; i++) {
        if(!done[i]) {
            done[i] = 1;
            to.push_back(-abs(S[i]));
            to.push_back(abs(S[i]));
            m[S[i]+n].pop();
            done[m[-S[i]+n].top()] = 1;
            m[-S[i]+n].pop();
        }
    }
    return find_swaps(S, to);
}

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