제출 #1114858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114858		anmattroi	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	70 ms	10588 KiB

shoes

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


using namespace std;

long long count_swaps(std::vector<int> s) {
    int n = int(s.size()) / 2;
    s.insert(s.begin(), 0);

    vector<int> bit(n+n+1, 0), a(n+n+1, 0);
    vector<int> b(1);
    for (int i = 1; i <= n+n; i++) {
        if (s[i] > 0) b.emplace_back(s[i]);
    }
    sort(b.begin()+1, b.end());
    for (int i = 1; i <= n+n; i++) {
        if (s[i] > 0) {
            s[i] = lower_bound(b.begin()+1, b.end(), s[i]) - b.begin();
        } else s[i] = -(lower_bound(b.begin()+1, b.end(), -s[i]) - b.begin());
    }


    function<void(int, int)> upd = [&](int u, int d) {
        for (int i = u; i > 0; i -= i & -i) bit[i] += d;
    };

    function<int(int)> get = [&](int u) {
        int kq = 0;
        for (int i = u; i <= n+n; i += i & -i) kq += bit[i];
        return kq;
    };

    vector<vector<int> > nho(n+1, vector<int>(0));

    int cnt = 0;


    for (int i = 1; i <= n+n; i++) {
        if (s[i]<0) {
            ++cnt;
            a[i] = cnt*2-1;
            nho[-s[i]].emplace_back(a[i]+1);
        }
    }
    for (int i = 1; i <= n; i++) reverse(nho[i].begin(), nho[i].end());

    for (int i = 1; i <= n+n; i++) {
        if (s[i]<0) continue;
        a[i] = nho[s[i]].back();
        nho[s[i]].pop_back();
    }
    long long kq = 0;
    for (int i = 1; i <= n+n; i++) {
        kq += get(a[i]);
        upd(a[i], 1);
    }
	return kq;
}

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