Submission #674989

#	Time	Username	Problem	Language	Result	Execution time	Memory
674989		VodkaInTheJar	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	73 ms	21616 KiB

shoes

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

using namespace std;

const int maxn = 1e5 + 3;

int tr[maxn];
void update(int pos, int val) {
    for (; pos < maxn; pos += pos & -pos)
        tr[pos] += val;
}

int get(int pos) {
    int ans = 0;
    for (; pos > 0; pos -= pos & -pos)
        ans += tr[pos];

    return ans;
}

long long count_inversions(vector <int> v) {
    long long ans = 0; 
    for (int i = (int)v.size()-1; i >= 0; i--) {
        ans += get(v[i]-1);
        update(v[i], 1);
    }
    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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15