Submission #737127

#	Time	Username	Problem	Language	Result	Execution time	Memory
737127		tvladm2009	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	69 ms	15304 KiB

shoes

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

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int A[2 * N_MAX + 2];
vector <int> Minus[N_MAX + 2], Plus[N_MAX + 2];
int nxt[2 * N_MAX + 2];
bool used[2 * N_MAX + 2];

int BIT[2 * N_MAX + 2];
void update(int pos, int val) {
    for (int i = pos; i <= 2 * N_MAX; i += i & -i) {
        BIT[i] += val;
    }
}
int query(int pos) {
    int answer = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        answer += BIT[i];
    }
    return answer;
}

ll count_swaps(vector <int> S) {
    int N = (int) S.size() / 2;
    for (int i = 1; i <= 2 * N; i++) {
        A[i] = S[i - 1];
    }
    for (int i = 2 * N; i >= 1; i--) {
        if (A[i] < 0) {
            Minus[A[i] * -1].push_back(i);
        } else {
            Plus[A[i]].push_back(i);
        }
    }
    for (int i = 1; i <= 2 * N; i++) {
        if (used[i] == true) {
            continue;
        }
        used[i] = true;
        if (A[i] < 0) {
            if (Plus[A[i] * -1].empty() == false) {
                nxt[i] = Plus[A[i] * -1].back();
                Plus[A[i] * -1].pop_back();
            }
            Minus[A[i] * -1].pop_back();
        } else {
            if (Minus[A[i]].empty() == false) {
                nxt[i] = Minus[A[i]].back();
                Minus[A[i]].pop_back();
            }
            Plus[A[i]].pop_back();
        }
        used[nxt[i]] = true;
    }
    for (int i = 1; i <= 2 * N; i++) {
        used[i] = false;
    }

    ll answer = 0;
    for (int i = 1; i <= 2 * N; i++) {
        if (used[i] == false) {
            int j = nxt[i];
            int between = query(j - 1) - query(i);
            int swaps = (j - i - 1) - between;
            if (A[i] > 0) {
                swaps++;
            }
            answer += swaps;
            used[i] = true;
            used[j] = true;
            update(i, +1);
            update(j, +1);
        }
    }
    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