Submission #151727

#	Time	Username	Problem	Language	Result	Execution time	Memory
151727		mbrc	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	768 ms	151224 KiB

shoes

#include "shoes.h"
#include <map>
#include <set>
#include <algorithm>
#include <tuple>
#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 7;
int bit[maxn];

void upd(int x) {
    x++;
    while (x < maxn) {
        bit[x]++; x += x & (-x);
    }
}

int qry(int x) {
    int ans = 0; x++;
    while (x > 0) {
        ans += bit[x]; x -= x & (-x);
    }
    return ans;
}

vector < int > res;
map < int, queue < int > > M;
map < int, int > G;

long long count_swaps(std::vector<int> s) {
    
    int n = s.size(); M.clear(); G.clear();
    res.clear(); res.resize(n);
    int cur = 0;

    fill(bit, bit + n + n, 0);

    for (int j = 0; j < n; j++) {
        if (M.find(-s[j]) != M.end() && !M[-s[j]].empty()) {
            int z = M[-s[j]].front(); M[-s[j]].pop();
            int p = G[z];
            if (s[j] < 0) {
                res[p + p] = j; res[p + p + 1] = z;
            } else {
                res[p + p + 1] = j; res[p + p] = z;
            }
        } else {
            if (M.find(s[j]) == M.end()) M[s[j]] = *new queue < int >();
            M[s[j]].push(j);
            G[j] = cur++;
        }
    }

    ll ans = 0;

    //for (int x : res) {
        //cout << x << " ";
    //}
    //cout << endl;

    for (int j = n - 1; j >= 0; j--) {
        ans += qry(res[j]); upd(res[j]);
    }

    return ans;
}

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