Submission #482144

#	Time	Username	Problem	Language	Result	Execution time	Memory
482144		MasterTaster	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	95 ms	20312 KiB

shoes

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

#define ll long long
#define pb push_back
#define MAXN 200010

using namespace std;

int bit[MAXN+10], gde[MAXN];
vector<int> leva[MAXN], desna[MAXN];

void upd(int x)
{
    while (x<MAXN)
    {
        bit[x]++;
        x+=x&(-x);
    }
}

int sum(int x)
{
    ll ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}


ll ress;
long long count_swaps(std::vector<int> s) {
    ress=0;
    int n=s.size()/2;

    for (int i=0; i<2*n; i++)
    {
        if (s[i]>0) desna[s[i]].pb(i);
        else leva[-s[i]].pb(i);
    }

    for (int i=0; i<2*n; i++) gde[i]=-1;


    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<desna[i].size(); j++)
        {
            //cout<<leva[i][j]<<" "<<desna[i][j]<<endl;
            if (leva[i][j]<desna[i][j]) gde[leva[i][j]]=desna[i][j];
            else gde[desna[i][j]]=leva[i][j];
        }
    }

    for (int i=0; i<2*n; i++)
    {
        if (gde[i]!=-1)
        {
            //cout<<sum(gde[i]-1)<<" "<<sum(i-1)<<endl;
            if (i!=0)
            {
                if (s[i]<0) ress+=(gde[i]-(sum(gde[i]-1)-sum(i-1))-i-1);
                else ress+=(gde[i]-(sum(gde[i]-1)-sum(i-1))-i);
                upd(gde[i]);
            }
            else
            {
                if (s[i]<0) ress+=(gde[i]-(sum(gde[i]-1))-i-1);
                else ress+=(gde[i]-(sum(gde[i]-1))-i);
                upd(gde[i]);
            }
        }
    }
    return ress;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int j=0; j<desna[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