Submission #309544

#	Time	Username	Problem	Language	Result	Execution time	Memory
309544		lucaperju	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	68 ms	12200 KiB

shoes

//#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
long long fv[100005],ok[100005];
vector<long long>v[100005];
void next (long long &j)
{
    ++j;
    while(ok[j])
        ++j;
}
struct ura
{
    long long sum,val;
}vc[100005];
bool cmp (ura a, ura b)
{
    return a.sum<b.sum;
}
long long bc[100005];
long long aib[200005];
long long lsb (long long x)
{
    return x&-x;
}
void update (long long pz)
{
    for(long long i=pz;i<=200002;i+=lsb(i))
        ++aib[i];
}
long long query (long long pz)
{
    long long rz=0;
    for(long long i=pz;i>0;i-=lsb(i))
        rz+=aib[i];
    return rz;
}
long long count_swaps(std::vector<int> s) {
	long long n=s.size()/2;
	long long i,j,mx=0;
	for(i=0;i<s.size();++i)
	{
        if(s[i]>0)
            ++fv[s[i]],ok[s[i]]=1;
	}
    j=0;
    next(j);
    for(i=0;i<s.size();++i)
    {
        if(s[i]<0)
            continue;
        if(fv[s[i]]>1)
        {
            --fv[s[i]];
            v[s[i]].push_back(j);
            s[i]=j;
            next(j);
        }
        else
            fv[s[i]]=0;
    }
    for(i=0;i<s.size();++i)
        if(s[i]<0 && fv[-s[i]]<v[-s[i]].size())
            s[i]=-v[-s[i]][fv[-s[i]]++];
  //  for(i=0;i<s.size();++i)
  //      cout<<s[i]<<' ';
  //  cout<<'\n';
    for(i=1;i<=n;++i)
        fv[i]=0;
    long long rz=0;
    for(i=0;i<s.size();++i)
    {
        long long vlc=s[i];
        if(vlc<0)
            vlc=-vlc;
        vc[vlc].sum+=i;
        vc[vlc].val=vlc;
    }
    sort(vc+1,vc+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        bc[vc[i].val]=i;
    }
    for(i=0;i<s.size();++i)
    {
        if(s[i]>0)
            s[i]=bc[s[i]];
        else
            s[i]=-bc[-s[i]];
        if(s[i]<0)
            s[i]=2*(-s[i]-1)+1;
        else
            s[i]=2*(s[i]-1)+2;
    }
 //   for(i=0;i<s.size();++i)
 //       cout<<s[i]<<' ';
 //   cout<<'\n';
    for(i=s.size()-1;i>=0;--i)
    {
        rz+=query(s[i]);
        update(s[i]);
    }
    return rz;
}
/*long long main()
{
    long long n,i;
    cin>>n;
    vector<long long>idk;
    for(i=1;i<=n*2;++i)
    {
        long long a;
        cin>>a;
        idk.push_back(a);
    }
    cout<<count_swaps(idk);
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:42:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(i=0;i<s.size();++i)
      |          ~^~~~~~~~~
shoes.cpp:49:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i=0;i<s.size();++i)
      |             ~^~~~~~~~~
shoes.cpp:63:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(i=0;i<s.size();++i)
      |             ~^~~~~~~~~
shoes.cpp:64:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(s[i]<0 && fv[-s[i]]<v[-s[i]].size())
      |                      ~~~~~~~~~^~~~~~~~~~~~~~~~
shoes.cpp:72:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(i=0;i<s.size();++i)
      |             ~^~~~~~~~~
shoes.cpp:85:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(i=0;i<s.size();++i)
      |             ~^~~~~~~~~
shoes.cpp:41:16: warning: unused variable 'mx' [-Wunused-variable]
   41 |  long long i,j,mx=0;
      |                ^~

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