Submission #722873

#	Time	Username	Problem	Language	Result	Execution time	Memory
722873		GrandTiger1729	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	77 ms	15164 KiB

shoes

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n): n(_n){
        bit.resize(n + 1);
    }
    void add(int i, int u){
        for (; i <= n; i += i & -i)
            bit[i] += u;
    }
    int query(int i){
        int ret = 0;
        for (; i > 0; i -= i & -i)
            ret += bit[i];
        return ret;
    }
    int query(int l, int r){
        return query(r) - query(l);
    }
};

long long count_swaps(vector<int> s){
	auto a = s;
    int N = a.size(), n = N / 2;
    vector<vector<int>> pos(N + 1);
    for (int i = N - 1; i >= 0; i--)
        pos[n + a[i]].push_back(i);
    vector<int> idx(N, -1);
    int cnt = 0;
    for (int i = 0; i < N; i++){
        if (idx[i] != -1) continue;
        int j = i, k = pos[n - a[i]].back();
        pos[n + a[i]].pop_back();
        pos[n - a[i]].pop_back();
        if (a[j] > 0) swap(j, k);
        idx[j] = 2 * cnt, idx[k] = 2 * cnt + 1;
        cnt++;
    }
    long long ret = 0;
    BIT bit(N);
    for (int i = 0; i < N; i++){
        ret += bit.query(idx[i], N);
        bit.add(idx[i] + 1, 1);
    }
    return ret;
}

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