Submission #780597

#	Time	Username	Problem	Language	Result	Execution time	Memory
780597		Minindu206	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	138 ms	138920 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
const int MAXN = 1e5 + 5;
using namespace std;
queue<int> pos[MAXN], neg[MAXN];
struct fenwick
{
    int n;
    vector<int> fn;
    void init(int _n)
    {
        this->n = _n + 1;
        fn.resize(n, 0);
    }
    void update(int x, int y)
    {
        x++;
        while (x < n)
        {
            fn[x] += y;
            x += (x & (-x));
        }
    }
    int sum(int ind)
    {
        ind++;
        int ans = 0;
        while (ind)
        {
            ans += fn[ind];
            ind -= (ind & (-ind));
        }
        return ans;
    }
};
ll count_swaps(vector<int> s)
{
    int n = s.size() / 2;
    for (int i = 0; i < 2 * n; i++)
    {
        if (s[i] > 0)
            pos[s[i]].push(i);
        else
            neg[-s[i]].push(i);
    }
    vector<int> vis(2 * n);
    fenwick tree;
    tree.init((2 * n));
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++)
    {
        ll swps = 0;
        if (vis[i])
            continue;
        int nxt = (s[i] > 0 ? neg[s[i]].front() : pos[-s[i]].front());
        neg[abs(s[i])].pop();
        pos[abs(s[i])].pop();
        ans += (nxt - i - (s[i] < 0)) - (tree.sum(nxt) - tree.sum(i));
        tree.update(nxt + 1, 1);
        vis[i] = 1;
        vis[nxt] = 1;
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:53:12: warning: unused variable 'swps' [-Wunused-variable]
   53 |         ll swps = 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