Submission #387476

#	Time	Username	Problem	Language	Result	Execution time	Memory
387476		ruadhan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	77 ms	9192 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;
typedef pair<int, int> pi;

const int MAXN = 2e5 + 1;

int n;
int bit[MAXN];

void upd(int i, int v)
{
    for (; i <= 2 * n; i += i & -i)
        bit[i] += v;
}
ll sum(int i)
{
    ll res = 0;
    for (; i > 0; i -= i & -i)
        res += bit[i];
    return res;
}

ll count_swaps(vector<int> S)
{
    ll ans = 0;
    n = sz(S) / 2;
    vector<pi> swaps;
    vector<pi> idx[n + 1];

    for (int i = 0; i < 2 * n; i++)
        idx[abs(S[i])].push_back({S[i], i + 1});

    for (int i = 1; i <= n; i++)
    {
        sort(all(idx[i]));
        // for (auto x : idx[i])
        //     cout << x.first << " " << x.second << endl;
        for (int j = 0; j < sz(idx[i]) / 2; j++)
        {
            int l = idx[i][j].second;
            int r = idx[i][j + sz(idx[i]) / 2].second;
            if (l > r)
            {
                swap(l, r);
                ans++;
            }
            swaps.push_back({l, r});
        }
    }

    sort(all(swaps));

    // for (auto x : swaps)
    //     cout << x.first << " " << x.second << endl;

    for (int i = 1; i <= 2 * n; i++)
        upd(i, 1);

    // cout << "ans = " << ans << endl;
    for (auto s : swaps)
    {
        // ans += sum(s.second - 1) - sum(s.first);
        ans += sum(s.second - 1) - sum(s.first);
        upd(s.first, -1);
        // cout << "s = " << s.first << " " << s.second << endl;
        upd(s.second, -1);
    }

    return ans;
}

// int main()
// {
//     int t;
//     cin >> t;
//     vector<int> S(t * 2);
//     for (auto &x : S)
//         cin >> x;
//     // for (auto x : S)
//     //     cout << x << " ";
//     // cout << endl;
//     cout << count_swaps(S) << 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