Submission #773284

#	Time	Username	Problem	Language	Result	Execution time	Memory
773284		teokakabadze	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	192 ms	143308 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;

ll a[N], n, k[N], i, t[N];
queue<int> q[N];

void upd(ll a, ll d)
{
    for(; a <= n; a += (a & (-a)))
        t[a] += d;
}

ll get(ll a)
{
    int s = 0;
    for(; a > 0; a -= (a & (-a)))
    s += t[a];
    return s;
}

long long count_swaps(std::vector<int> s)
{
    ll b;
    n = s.size();
    ll ans = 0;
    for(i = 1; i <= n; i++)
    {
        a[i] = s[i - 1];
        if(a[i] < 0) k[i] = abs(a[i]);
        else k[i] = a[i] + 100000;
        upd(i, 1);
        q[k[i]].push(i);
    }
    for(i = 1; i <= n; i++)
    {
        //cout << k[i] << ' ';
        if(k[i] <= 100000) b = k[i] + 100000;
        else b = k[i] - 100000;

        if(q[k[i]].size() && q[k[i]].front() == i)
        {
            upd(i, -1);
            upd(q[b].front(), -1);
            ans += get(q[b].front());
            if(k[i] > 100000) ans++;
            q[k[i]].pop();
            q[b].pop();
        }
    }
	return ans;
}

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