Submission #289902

#	Time	Username	Problem	Language	Result	Execution time	Memory
289902		evpipis	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	113 ms	21248 KiB

shoes

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

#define pb push_back
typedef long long ll;
const int len = 2e5+5, mx = 2e5;
int vis[len], tree[len], shoe[len];
vector<int> lef[len], rig[len];

void upd(int i, int v){
    while (i <= mx)
        tree[i] += v, i += i&(-i);
}

int ask(int i){
    int ans = 0;
    while (i > 0)
        ans += tree[i], i -= i&(-i);
    return ans;
}

ll count_swaps(vector<int> S) {
    ll ans = 0;
    int n = S.size();

    for (int i = 1; i <= n; i++)
        shoe[i] = S[i-1];

    for (int i = n; i >= 1; i--){
        if (shoe[i] > 0) rig[shoe[i]].pb(i);
        else lef[-shoe[i]].pb(i);

        upd(i, +1);
    }

    for (int i = 1; i <= n; i++){
        if (vis[i]) continue;

        int j = lef[abs(shoe[i])].back();
        if (shoe[i] < 0)
            j = rig[abs(shoe[i])].back();

        ans += ask(j)-2 + (shoe[i] > 0);

        vis[i] = vis[j] = 1;
        upd(i, -1), upd(j, -1);
        lef[abs(shoe[i])].pop_back();
        rig[abs(shoe[i])].pop_back();
    }

	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