Submission #724535

#	Time	Username	Problem	Language	Result	Execution time	Memory
724535		Kormuyang	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	68 ms	12548 KiB

shoes

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<pii> vec;
vector<pii> ind[200010];

struct BIT {
    int tree[200010];
    void add(int idx, int val) {
        for(int i = idx; i < 200010; i += (i & -i)) tree[i] += val;
        return;
    }
    int query(int idx) {
        int temp = 0;
        for(int i = idx; i > 0; i -= (i & -i)) temp += tree[i];
        return temp;
    }
} bit;

ll count_swaps(vector<int> s) {
    int n = ((int) s.size()) / 2;
    ll res = 0;
    for(int i = 0; i < (int) s.size(); i++) {
        ind[abs(s[i])].emplace_back(s[i], i);
    }
    for(int i = 1; i <= n; i++) {
        sort(ind[i].begin(), ind[i].end());
        for(int j = 0; j < ((int) ind[i].size()) / 2; j++) {
            int l = ind[i][j].second, r = ind[i][j + ((int) ind[i].size()) / 2].second;
            if(l > r) {
                swap(l, r); res++;
            }
            vec.emplace_back(l + 1, r + 1);
        }
    }
    for(int i = 1; i <= 2 * n; i++) bit.add(i, 1);
    sort(vec.begin(), vec.end());
    for(auto i : vec) {
        res += (bit.query(i.second - 1) - bit.query(i.first));
        bit.add(i.first, -1);
        bit.add(i.second, -1);
    }
    return res;
}

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