Submission #1040947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040947		idas	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 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

#define int long long

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

//    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()){
        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);

    return true_ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc9ug8iZ.o: in function `main':
grader.cpp:(.text.startup+0x2a8): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status