Submission #590765

#	Time	Username	Problem	Language	Result	Execution time	Memory
590765		DAleksa	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	68 ms	16024 KiB

shoes

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

using namespace std;

template<typename T, int start>
class Fenwick {
    private:
        const T operation_neutral = 0;
        T operation(T a, T b) { return a + b; }
        T inverseOperation(T a, T b) { return a - b; }
    public:
        vector<T> fenwick;
        int n;
        Fenwick(int _n) {
            n = _n;
            fenwick.resize(n);
            fill(fenwick.begin(), fenwick.end(), operation_neutral);
        }
        void update(int x, T v) {
            for(int i = x + 1 - start; i <= n - start; i += (i & -i)) {
                fenwick[i - 1 + start] = operation(fenwick[i - 1 + start], v);
            }
        }
        T get(int x) {
            T v = operation_neutral;
            for(int i = x + 1 - start; i >= 1; i -= (i & -i)) {
                v = operation(v, fenwick[i - 1 + start]);
            }
            return v;
        }
        T get(int l, int r) {
            if(l == start) return get(r);
            return inverseOperation(get(r), get(l-1));
        }
};

long long count_swaps(vector<int> a) {
    int n = a.size();
    vector<int> left[n / 2 + 1], right[n / 2 + 1];
    for(int i = 0; i < n; i++) {
        if(a[i] < 0) left[-a[i]].push_back(i);
        else right[a[i]].push_back(i);
    }
    int cnt[n / 2 + 1];
    for(int i = 0; i <= n / 2; i++) cnt[i] = 0;
    int pos[n];
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] < 0) {
            pos[i] = c;
            pos[right[-a[i]][cnt[-a[i]]]] = c + 1;
            cnt[-a[i]]++;
            c += 2;
        }
    }
    Fenwick<int, 0> fw(n);
    long long res = 0;
    for(int i = 0; i < n; i++) {
        res += fw.get(pos[i] + 1, n - 1);
        fw.update(pos[i], 1);
    }
    return res;
}

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