Submission #143868

#	Time	Username	Problem	Language	Result	Execution time	Memory
143868		Bodo171	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	113 ms	19960 KiB

shoes

#include "shoes.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=200005;
vector<int> v[2][nmax];
struct pr
{
    int x,y;
}a[nmax];
bool comp(pr unu,pr doi)
{
    return ((unu.x+unu.y)<(doi.x+doi.y));
}
int fin[nmax],po[nmax];
int nr,i,j,mn,col,poz;
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
int n;
int aib[nmax];
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=2*n;idx+=lbit(idx))
        aib[idx]+=val;
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
long long count_swaps(vector<int> s) {
    n=s.size();
    n/=2;long long ans=0;
    for(int i=0;i<2*n;i++)
    {
        v[(s[i]>0)][abss(s[i])].push_back(i);
    }
    ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<v[0][i].size();j++)
        {
            a[nr++]={v[0][i][j],v[1][i][j]};
        }
    }
    sort(a,a+nr,comp);
    for(i=0;i<nr;i++)
    {
        fin[a[i].x]=2*i;
        fin[a[i].y]=2*i+1;
    }
    for(i=0;i<2*n;i++)
    {
        ans+=1LL*(i-1LL*compute(fin[i]+1));
        update(fin[i]+1,1);
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<v[0][i].size();j++)
                 ~^~~~~~~~~~~~~~~

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