Submission #1040951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040951		idas	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	127 ms	13784 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<ll> vi;

const int N=2e5+10;
ll n, cn[N], pos[N];
vi p_pos, n_pos[N];

void upd_cn(int p, int x)
{
    p++;
    for(int i=p; i<N; i+=i&(-i)) cn[i]+=x;
}

ll get_cn_pref(int p)
{
    p++;
    ll ret=0;
    for(int i=p; i>0; i-=i&(-i)) ret+=cn[i];
    return ret;
}

ll get_cn(int x, int y)
{
    x++; y++;
    return get_cn_pref(y)-get_cn_pref(x-1);
}

void upd_pos(int p, int x)
{
    p++;
    for(int i=p; i<N; i+=i&(-i)) pos[i]+=x;
}

ll add_pos(int p)
{
    p++;
    ll ret=0;
    for(int i=p; i>0; i-=i&(-i)) ret+=pos[i];
    return ret;
}

ll get_pos(int p)
{
    return 1LL*p+add_pos(p);
}

void shift(int p, int x)
{
    int l=p, r=n-1;
    while(l<r){
        int m=(l+r+1)/2;
        if(get_cn(p, m)<=x) l=m;
        else r=m-1;
    }
    upd_pos(p, -1);
    upd_pos(l+1, 1);
}

long long count_swaps(vector<int> s) {
    ll true_ans=1e18;
    n=s.size();

    FOR(i, 0, n)
    {
        if(s[i]<0) n_pos[-s[i]].pb(i);
        else p_pos.pb(i);
    }
    FOR(i, 0, n) upd_cn(i, 1);
    ll ans=0;
    ll in=n-1;
    while(!p_pos.empty()){
        ll pos=p_pos.back();
        p_pos.pop_back();
        upd_cn(pos, -1);
        ll  true_pos=get_pos(pos);
        assert(in>=true_pos);
        ll dist=in-true_pos; ans+=dist;
        in--;
        shift(pos, dist);
        ll neg_pos=n_pos[s[pos]].back();
        n_pos[s[pos]].pop_back();
        upd_cn(neg_pos, -1);
        ll true_neg_pos=get_pos(neg_pos);
        dist=in-true_neg_pos; ans+=dist;
        in--;
        shift(neg_pos, dist);
    }
    true_ans=min(true_ans, ans);

//    FOR(i, 0, n) s[i]=-s[i];
    FOR(i, 0, N) cn[i]=pos[i]=0, n_pos[i].clear();
    p_pos.clear();
    reverse(s.begin(), s.end());

    FOR(i, 0, n)
    {
        if(s[i]>0) n_pos[s[i]].pb(i);
        else p_pos.pb(i);
    }
    FOR(i, 0, n) upd_cn(i, 1);

    ans=0;
    in=n-1;
    while(!p_pos.empty()){
        ll pos=p_pos.back();
        p_pos.pop_back();
        upd_cn(pos, -1);
        ll true_pos=get_pos(pos);
        assert(in>=true_pos);
        ll dist=in-true_pos; ans+=dist;
        in--;
        shift(pos, dist);
        ll neg_pos=n_pos[-s[pos]].back();
        n_pos[-s[pos]].pop_back();
        upd_cn(neg_pos, -1);
        ll true_neg_pos=get_pos(neg_pos);
        dist=in-true_neg_pos; ans+=dist;
        in--;
        shift(neg_pos, dist);
    }
    true_ans=min(true_ans, ans);

    return true_ans;
}

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