Submission #1200971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200971		nvc2k8	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	30 ms	9664 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;
vector<int> rshoes[100005];
int ptr[100005];
int a[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.pb(i+1);
        else
        {
            rshoes[s[i]].pb(i+1);
        }
    }

    int cur = 0;
    for (auto i:lshoes)
    {
        a[i] = ++cur;
        int ss = -s[i-1];
        a[rshoes[ss][ptr[ss]++]] = ++cur;
    }

    ll ret = 0;

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

    return ret;
}

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