제출 #199342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199342		mythos	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	107 ms	12788 KiB

shoes

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

using namespace std;

const int maxn = 200200;

struct Fenwick {
    int tree[maxn];

    void set(int x, int v) {
        for (int i = x; i < maxn; i += i & -i) tree[i] += v;
    }

    int get(int x) {
        int res = 0;
        for (int i = x; i; i -= i & -i) res += tree[i];
        return res;
    }
} bit;

long long count_swaps(vector<int> s) {
    int n = (int) s.size() / 2;
    long long res = 0;
    vector<pair<int, int> > v;
    vector<pair<int, int> > ord[maxn];

    for (int i = 0; i < (int) s.size(); i++) {
        ord[abs(s[i])].emplace_back(s[i], i);
    }

    for (int i = 1; i <= n; i++) {
        sort(ord[i].begin(), ord[i].end());
        for (int j = 0; j < (int) ord[i].size() / 2; j++) {
            int l = ord[i][j].second;
            int r = ord[i][j + (int) ord[i].size() / 2].second;
            if (l > r) {
                swap(l, r); res++;
            }
            v.emplace_back(l + 1, r + 1);
        }
    }

    for (int i = 1; i <= 2 * n; i++) bit.set(i, 1);
    sort(v.begin(), v.end());

    for (auto i : v) {
        res += bit.get(i.second - 1) - bit.get(i.first);
        bit.set(i.first, -1);
        bit.set(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