Submission #159196

#	Time	Username	Problem	Language	Result	Execution time	Memory
159196		Mathew	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1072 ms	135032 KiB

shoes

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

long long n,to[200050],pairs=0,br=0;
queue <long long> found[200050];
long long from[200050],perm[200050];

int tree[MAX+1];

int query(int idx)
{
    int sum=0;
    for(; idx < MAX;idx+=(idx & -idx))sum+=tree[idx];
    return sum;
}

void update(int idx, int delta)
{
    for(; idx >0;idx-=(idx & -idx))tree[idx]+=delta;
}

long long count_swaps(vector <int> shoes)
{
    long long i,j;
    n=shoes.size()/2;
    for(i=0;i<2*n;i++)perm[i]=i;
    for(i=0;i<2*n;i++)
    {
        if(shoes[i]<0)
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs;
                found[n-shoes[i]].push(pairs+1);
                pairs+=2;
            }
        }
        
        else
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs+1;
                found[n-shoes[i]].push(pairs);
                pairs+=2;
            }
        }
    }
    
    for(i=0;i<2*n;i++)from[to[i]]=i;
    
    //for(i=0;i<2*n;i++)cout<<to[i]<<' ';cout<<endl;
    //for(i=0;i<2*n;i++)cout<<from[i]<<' ';cout<<endl;
    
    for(i=0;i<2*n;i++)
    {
        int curr=query(from[i])+from[i];
        br+=(long long)abs(curr-i);
        update(from[i],1);
    }
    return br;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:25:17: warning: unused variable 'j' [-Wunused-variable]
     long long i,j;
                 ^

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