Submission #1165170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165170		chikien2009	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	139 ms	139832 KiB

shoes

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

using namespace std;

// inline void setup()
// {
// #ifndef ONLINE_JUDGE
//     freopen("test.inp", "r", stdin);
//     freopen("test.out", "w", stdout);
// #endif
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
// }

class FENWICK_TREE
{
private:
    long long tree_size;
    vector<long long> tree;

public:
    FENWICK_TREE(long long new_size)
    {
        tree_size = new_size;
        tree.resize(tree_size + 1, 0);
    }
    void Update(long long pos, long long val)
    {
        while (pos <= tree_size)
        {
            tree[pos] += val;
            pos += pos & (~(pos - 1));
        }
    }
    long long Get(long long pos)
    {
        long long res = 0;
        while (0 < pos)
        {
            res += tree[pos];
            pos -= pos & (~(pos - 1));
        }
        return res;
    }
};

long long count_swaps(vector<int> S)
{
    int a;
    long long res = 0;
    queue<long long> neg[S.size() / 2 + 1], pos[S.size() / 2 + 1];
    FENWICK_TREE ft(S.size());
    S.insert(S.begin(), 0);
    for (long long i = 1; i < S.size(); ++i)
    {
        if (S[i] < 0)
        {
            neg[-S[i]].push(i);
        }
        else
        {
            pos[S[i]].push(i);
        }
    }
    for (long long i = 1, j = 1; i < S.size(); ++i)
    {
        if (S[i] == 0)
        {
            continue;
        }
        if (S[i] < 0)
        {
            a = pos[-S[i]].front();
            res += a - i - (ft.Get(a) - ft.Get(i - 1)) - 1;
        }
        else
        {
            a = neg[S[i]].front();
            res += a - i - (ft.Get(a) - ft.Get(i - 1));
        }
        S[a] = 0;
        ft.Update(a, 1);
        pos[abs(S[i])].pop();
        neg[abs(S[i])].pop();
    }
    return res;
}

// int main()
// {
//     setup();

//     long long n;
//     vector<int> v;
//     cin >> n;
//     v.resize(n);
//     for (long long i = 0; i < n; ++i)
//     {
//         cin >> v[i];
//     }
//     cout << count_swaps(v);
//     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