Submission #1100916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100916		Zero_OP	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	53 ms	16236 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val){
        for(; id > 0; id -= id & (-id)){
            bit[id] += val;
        }
    }

    int query(int id){
        int sum = 0;
        for(; id < (int)bit.size(); id += id & (-id)){
            sum += bit[id];
        }
        return sum;
    }
};

long long count_swaps(vector<int> S){
    int n = (int)S.size() / 2;
    vector<vector<int>> left(n + 1), right(n + 1);

    for(int i = 0; i < (int)S.size(); ++i){
        if(S[i] < 0) left[-S[i]].push_back(i);
        else right[S[i]].push_back(i);
    }

//    for(int i = 1; i <= n; ++i){
//        cout << i << " : ";
//        for(int x : left[i]) cout << x << ' '; cout << '\n';
//        for(int x : right[i]) cout << x << ' '; cout << '\n';
//    }

    vector<int> a((int)S.size());
    vector<bool> vis(n + 1, false);
    int timerNode = 0;

    vector<bool> deleted((int)S.size());
    vector<int> used(n + 1);
    for(int i = 0; i < (int)S.size(); ++i){
        if(deleted[i]) continue;
        int x = abs(S[i]);

        int u = left[x][used[x]];
        int v = right[x][used[x]];
        ++used[x];

        a[u] = ++timerNode;
        a[v] = ++timerNode;
        deleted[u] = true;
        deleted[v] = true;
    }

    Fenwick T((int)S.size());
    long long inv = 0;
    for(int i = 0; i < (int)S.size(); ++i){
//        cout << a[i] << ' ';
        inv += T.query(a[i]);
        T.update(a[i], +1);
    }
//    cout << '\n';
    return inv;
}

#ifdef LOCAL
int main(){
    cout << count_swaps({2, 1, -1, -2}) << '\n';
    cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';
}
#endif

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