Submission #773281

#	Time	Username	Problem	Language	Result	Execution time	Memory
773281		teokakabadze	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1092 ms	135060 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[b].size()) % 2 == 0)
        {
            upd(i, -1);
            upd(q[b].front(), -1);
            ans += get(q[b].front());
            if(k[i] > 100000) ans++;
        }
        q[k[i]].pop();
    }
	return ans;
}

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