Submission #674979

#	Time	Username	Problem	Language	Result	Execution time	Memory
674979		VodkaInTheJar	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1085 ms	21024 KiB

shoes

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

long long count_inversions(vector <int> v) {
    long long ans = 0; 
    for (int i = 0; i < (int)v.size(); i++)
        for (int j = i + 1; j < (int)v.size(); j++)
            if (v[i] > v[j])
                ans++;

    return ans; 
}

long long count_swaps(vector <int> s) {
    int n = (int)s.size();
    vector <vector <int> > left(n), right(n);
    for (int i = 0; i < n; i++) {
        if (s[i] < 0)
            left[-s[i]].push_back(i);

        else 
            right[s[i]].push_back(i);
    }

    vector <int> perm(n), idx(n, 0);
    vector <bool> used(n, false);
    int el = 1, cnt = 0; 
    for (int i = 0; i < n; i++) {
        if (used[i])
            continue;
    
        int other;
        if (s[i] < 0)
            other = right[-s[i]][idx[-s[i]]++];

        else 
            other = left[s[i]][idx[s[i]]++], cnt++;

        used[other] = true;
        perm[i] = perm[other] = el++; 
    }
    
    //for (auto i: perm)
     //   cout << i << " ";
    //cout << endl; 

    return count_inversions(perm) + cnt;
}

/*
int n; 
int main() {
	cin >> n;
    vector <int> v(n + n);
    for (int i = 0; i < n + n; i++)
        cin >> v[i];

    cout << count_swaps(v) << endl; 
}
*/

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