Submission #1201001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201001		nvc2k8	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	41 ms	15432 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define TASK "shoes"
#define INT_LIM (int) 2147483647
#define LL_LIM (long long) 9223372036854775807
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define ll long long
#define pii pair<int,int>
using namespace std;
///------------------------------------------///
int n;
vector<int> lshoes[100005];
vector<int> rshoes[100005];
int lptr[100005], rptr[100005];
int a[200005];
bool dd[200005];
int f[200005];

void update(int u, int delta)
{
    for (int i = u; i<=n; i+=(i&(-i))) f[i]+=delta;
}

int get(int u)
{
    int ret = 0;
    for (int i = u; i>0; i-=(i&(-i))) ret+= f[i];
    return ret;
}

ll count_swaps(vector<int> s)
{
    n = s.size();
    FOR(i, 0, n-1)
    {
        if (s[i]<0)
        {
            lshoes[-s[i]].pb(i);
        }
        else
        {
            rshoes[s[i]].pb(i);
        }
    }

    int cur = 0;
    for (int i = 0; i<n; i++) if (!dd[i])
    {
        int ss = abs(s[i]);
        int x = lshoes[ss][lptr[ss]];
        int y = rshoes[ss][rptr[ss]];
        dd[x] = true; dd[y] = true;
        lptr[ss]++; rptr[ss]++;
        a[x+1] = ++cur;
        a[y+1] = ++cur;
    }

    ll ret = 0;

    FORD(i, n, 1)
    {
        ret+= (ll) get(a[i]);
        update(a[i], 1);
    }

    return ret;
}

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