Submission #577894

#	Time	Username	Problem	Language	Result	Execution time	Memory
577894		mi_ni_	Arranging Shoes (IOI19_shoes)	C++17	70 / 100	1102 ms	294148 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());
    map<int, stack<int>> s;
    int n = from.size();
    for(int ind = n-1; ind >= 0; ind--) s[to[ind]].push(ind);
    vector<int> pos;
    for(auto i:from) {
        pos.push_back(s[i].top());
        s[i].pop();
    }
    return find_inversions(pos, 0, n-1);
}

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

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0; i<S.size(); i++) {
      |                  ~^~~~~~~~~

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