Submission #303824

#	Time	Username	Problem	Language	Result	Execution time	Memory
303824		noob_c0de	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	19 ms	19456 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#define ar array
const int mxn=2e5+3;
int n;
vector<int> pos[mxn],neg[mxn];
int ft[2*mxn];
int vis[mxn];
void upd(int u,int d)
{
    while(u<=n)
    {
        ft[u]+=d;
        u+=u&-u;
    }
}
int get(int u)
{
    int res=0;
    while(u)
    {
        res+=ft[u];
        u-=u&-u;
    }
    return res;
}
int count_swaps(vector<int> a)
{
    n=a.size();
    for (int i=n;i>=1;i++)
    {
        if (a[i-1]>0) pos[a[i-1]].push_back(i);
        else neg[-a[i-1]].push_back(i);
    }
    int ans=0;
    for (int i=1;i<=n;i++)
    if (!vis[i])
    {
        int vt;
        if (a[i-1]>0) vt=neg[a[i-1]].back();
        else vt=pos[-a[i-1]].back();
        pos[abs(a[i-1])].pop_back();
        neg[abs(a[i-1])].pop_back();
        ans+=(vt+get(vt))-(i+get(i))-1;
        if (a[i-1]>0) ans++;
        upd(1,1);
        if (vt+1<=n) upd(vt+1,-1);
        vis[vt]=1;
    }
    return(ans);
}

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