Submission #1040914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040914		idas	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	75 ms	12548 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)
{
//    cout << "shift: " << p << " " << x << endl;
    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;
//        cout << l << " " << m << endl;
    }
    upd_pos(p, -1);
    upd_pos(l+1, 1);
//    cout << p << " " << x << endl;
}

long long count_swaps(vector<int> s) {
    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;
    int in=n-1;
    while(!p_pos.empty()){
        int pos=p_pos.back();
        p_pos.pop_back();
        upd_cn(pos, -1);

//        cout << "positive position: " << pos << endl;

        int true_pos=get_pos(pos);

//        cout << "true: " << true_pos << endl;

        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);

//        cout << "negative position: " << neg_pos << endl;

        int true_neg_pos=get_pos(neg_pos);
        dist=in-true_neg_pos; ans+=dist;
        in--;

//        cout << "true: " << true_neg_pos << endl;

//        cout <<"dist: " << dist << endl;
        shift(neg_pos, dist);
    }

    return 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