Submission #387460

#	Time	Username	Problem	Language	Result	Execution time	Memory
387460		ruadhan	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	61 ms	94316 KiB

shoes

#include <bits/stdc++.h>
typedef long long ll;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

using namespace std;

const int MAXN = 2e6 + 1;
bool swapped[MAXN];
int n;

struct BIT
{
    vector<int> e;
    void init(int n) { e = vector<int>(n, 0); }
    void upd(int i, int v)
    {
        for (; i <= n; i += i & -i)
            e[i] += v;
    }
    ll sum(int r)
    {
        ll res = 0;
        for (; r; r -= r & -r)
            res += e[r];
        return res;
    }
    ll qry(int l, int r) { return sum(r) - sum(l - 1); }
};

BIT ft;
vector<int> Sh;
set<int> idx[MAXN / 2][2];
ll ans = 0;
void swap(int i)
{
    auto swap_idx = begin(idx[abs(Sh[i])][0]);
    if (abs(*swap_idx - i) == 1)
    {
        if (*swap_idx < i)
            ans++;
    }
    else
    {
        ans += abs(*swap_idx - i) + ft.qry(min(*swap_idx, i), max(*swap_idx, i));
        ft.upd(*swap_idx, -1);
        ft.upd(i, 1);
    }
    idx[abs(Sh[i])][0].erase(swap_idx);
    idx[abs(Sh[i])][1].erase(idx[abs(Sh[i])][1].find(i));
}

ll count_swaps(vector<int> S)
{
    n = sz(S);
    S.insert(begin(S), {0});
    Sh = S;
    ft.init(n + 1);

    for (int i = 1; i <= n; i++)
    {
        if (Sh[i] < 0)
            idx[abs(Sh[i])][1].insert(i);
        else
            idx[Sh[i]][0].insert(i);
    }

    for (int i = 1; i <= n; i++)
    {
        if (i % 2 == 0) // even should have right shoe
        {
            if (Sh[i] > 0)
                continue;
            else
            {
                if (idx[abs(S[i])][1].count(i) != 0)
                {
                    swap(i);
                }
            }
        }
        else // odd should have odd shoe
        {
            if (Sh[i] < 0)
            {
                // swap if next not > 0
                if (idx[abs(S[i])][1].count(i) != 0)
                {
                    swap(i);
                }
            }
            else
            {
                continue;
            }
        }
    }
    return ans;
}

// int main()
// {
//     int n;
//     cin >> n;
//     vector<int> s(2 * n);
//     for (auto &x : s)
//         cin >> x;
//     cout << count_swaps(s) << endl;
//     return 0;
// }

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