Submission #1040932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040932		idas	Arranging Shoes (IOI19_shoes)	C++17	15 / 100	130 ms	11868 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<int> vi;

const int N=2e5+10;
int 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;
}

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

int 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;
}

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

int get_pos(int p)
{
    return 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(z, 0, 2)
    {
        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;
        int in=n-1;
        while(!p_pos.empty()){
            int pos=p_pos.back();
            p_pos.pop_back();
            upd_cn(pos, -1);
            int true_pos=get_pos(pos);
            assert(in>=true_pos);
            ll dist=in-true_pos; ans+=dist;
            in--;
            shift(pos, dist);
            int neg_pos=n_pos[s[pos]].back();
            n_pos[s[pos]].pop_back();
            upd_cn(neg_pos, -1);
            int 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);
        if(z==1) break;
        FOR(i, 0, n) s[i]=-s[i];
        FOR(i, 0, N) cn[i]=pos[i]=0, n_pos[i].clear();
        p_pos.clear();
    }

    return true_ans;
}

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