Submission #210385

#	Time	Username	Problem	Language	Result	Execution time	Memory
210385		HNO2	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	8 ms	4984 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
//#define int ll

#ifdef HNO2
#define IOS
#else
#include "shoes.h"
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

struct BIT
{
    ll d[maxn*2],N;

    void init(int _n)
    {
        N=_n;
        memset(d,0,sizeof(d));
    }

    void modify(int x,int dd)
    {
        for (int i=x;i<=N;i+=(i&(-i))) d[i]+=dd;
    }

    ll query(int x)
    {
        if (x==0) return 0;
        ll ret=0;
        for (int i=x;i>0;i-=(i&(-i))) ret+=d[i];
        return ret;
    }
}bit;

int a[maxn*2];
vector<int> L[maxn],R[maxn];
int p[maxn];

long long count_swaps(std::vector<int> S)
{
    int n=sz(S)/2;
    for (int i=1;i<=(n<<1);i++) a[i]=S[i-1];

    ll ans=0;
    for (int i=1;i<=(n<<1);i++)
    {
        if (a[i]>0)
        {
            if (sz(L[a[i]])>0)
            {
                p[L[a[i]].back()]=i;
                L[a[i]].pop_back();
            }
            else
            {
                R[a[i]].pb(i);
            }
        }
        else
        {
            if (sz(R[-a[i]])>0)
            {
                p[R[-a[i]].back()]=i;
                R[-a[i]].pop_back();
                ans++;
            }
            else
            {
                L[-a[i]].pb(i);
            }
        }
        //v[abs(a[i])].pb(i);
        //if (sz(v[abs(a[i])])==1&&a[i]>0) ans++;
    }
    return ans;
    bit.init(n<<1);
    for (int i=1;i<=(n<<1);i++)
    {
        if (p[i])
        {
            int nex=p[i];
            ans+=(nex-i-1)-(bit.query(nex)-bit.query(i));
            bit.modify(i,1);
            bit.modify(nex,1);
        }
    }
    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