Submission #483216

#	Time	Username	Problem	Language	Result	Execution time	Memory
483216		lukaszgniecki	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	147 ms	140768 KiB

shoes

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

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)

using namespace std;

//TODO: SOLUTION

void mktr(vi & T, int n) {
    int m = 1;
    while (m < n)
        m *= 2;
    T = vi(2 * m, 1);
    for (int i = m - 1; i > 0; i--) {
        T[i] = T[2 * i] + T[2 * i + 1];
    }
}

void upd(vi & T, int x, int y) {
    x += T.size() / 2;
    T[x] = y;
    x /= 2;
    while (x > 0) {
        T[x] = T[2 * x] + T[2 * x + 1];
        x /= 2;
    }
}

int get_sum(vi & T, int l, int r) {
    int sum = 0;
    l += T.size() / 2;
    r += T.size() / 2;

    while (l <= r) {
        if (l == 0 && r == 0)
            return sum;
        if (l % 2 == 1) {
            sum += T[l++];
        }
        if (r % 2 == 0) {
            sum += T[r--];
        }
        l /= 2;
        r /= 2;
    }
    return sum;
}

ll count_swaps(vi shoes) {
    int n = shoes.size() / 2;

    ll ans = 0;
    vector<queue<int>> pos(2 * n + 1);
    rep(i, 0, 2 * n) {
        int x = shoes[i];
        if (shoes[i] < 0)
            x = -x + n;
        pos[x].push(i);
    }

    vi tr;
    mktr(tr, 2*n);
    int m = tr.size() / 2;

    rep(i, 0, 2 * n) {
        if (tr[m + i] == 0)
            continue;

        int x = shoes[i];
        int y = x + n;
        if (x < 0) {
            y = -x;
            x = -x + n;
        }

        int ps = pos[y].front();
        pos[y].pop();
        pos[x].pop();

        ll moves = get_sum(tr, i + 1, ps - 1);
        if (y > n)
            moves++;
        //cerr << i << " " << ps << " " << moves << endl;

        ans += moves;

        upd(tr, ps, 0);
    }

    return ans;
}


/*int main() {
    vi sh1 = {2, 1, -1, -2};
    vi sh2 = {-2, 2, 2, -2, -2, 2};
    vi sh3 = {-2, -2, -1, -1, 1, 1, 2, 2};
    vi sh4 = {1, -1, -1, 1};
    cout << count_swaps(sh1) << endl;
    cout << count_swaps(sh2) << endl;
    cout << count_swaps(sh3) << endl;
    cout << count_swaps(sh4) << endl;
    return 0;
}*/

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