Submission #1175504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175504		KindaNameless	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	107 ms	138244 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct BIT {
    vector<int> fen;
    int N;

    BIT(int _N) {
        N = _N + 5;
        fen = vector<int>(N + 5, 0);
    }

    void upd(int x, int v) {
        x++;
        while(x <= N) {
            fen[x] += v;
            x += (x & -x);
        }
    }

    int prefix(int x) {
        x++;
        int res = 0;
        while(x > 0) {
            res += fen[x];
            x -= x & -x;
        }
        return res;
    }

    int query(int l, int r) {
        return prefix(r) - prefix(l - 1);
    }
};

deque<int> pos[2][100001];

ll count_swaps(vector<int> S) {
    int N = S.size();
    int n = N / 2;

    for(int i = 0; i < N; ++i) {
        if(S[i] < 0) {
            pos[0][-S[i]].push_back(i);
        }
        else {
            pos[1][S[i]].push_back(i);
        }
    }

    BIT bit(N);

    for(int i = 0; i < N; ++i) {
        bit.upd(i, 1);
    }

    ll answer = 0;
    vector<bool> used(N, 0);

    int counter = 0, i = 0;
    while(counter < n) {
        if(used[i]) {
            i++;
            continue;
        }
        if(S[i] < 0) {
            pos[0][-S[i]].pop_front();
            int j = pos[1][-S[i]].front(); pos[1][-S[i]].pop_front();

            answer += (ll)bit.query(i, j) - 2;

            bit.upd(i, -1); used[i] = 1;
            bit.upd(j, -1); used[j] = 1;
        }
        else {
            pos[1][S[i]].pop_front();
            int j = pos[0][S[i]].front(); pos[0][S[i]].pop_front();
            
            answer += (ll)bit.query(i, j) - 1;
            
            bit.upd(i, -1); used[i] = 1;
            bit.upd(j, -1); used[j] = 1;
        }
        counter++;
        i++;
    }

    return answer;
}

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