Submission #529571

#	Time	Username	Problem	Language	Result	Execution time	Memory
529571		groshi	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	332 KiB

shoes

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
map<int,vector<int> > mapka;
int pot=1;
int drzewo[600000];
bool mam[600000];
void usun(int x)
{
    x+=pot;
    drzewo[x]--;
    x/=2;
    while(x>=1)
    {
        drzewo[x]=drzewo[x*2]+drzewo[x*2+1];
        x/=2;
    }
}
int ile(int x,int y)
{
    x+=pot;
    y+=pot;
    int wynik=0;
    wynik+=drzewo[x];
    if(x!=y)
        wynik+=drzewo[y];
    while(x/2!=y/2)
    {
        if(x%2==0)
            wynik+=drzewo[x+1];
        if(y%2==1)
            wynik+=drzewo[y-1];
        x/=2;
        y/=2;
    }
    return wynik;
}
long long count_swaps(vector<int> S)
{
    while(pot<=S.size())
        pot*=2;
    pot--;
    for(int i=0;i<S.size();i++)
    {
        mapka[S[i]].push_back(i);
    }
    for(int i=1;i<=S.size();i++)
        drzewo[i+pot]=1;
    for(int i=pot;i>=1;i--)
        drzewo[i]=drzewo[i*2+1]+drzewo[i*2];
    long long wynik=0;
    for(int i=0;i<S.size();i++)
    {
        if(mam[i]==1)
            continue;
        mam[i]=1;
        if(S[i]>0)
            wynik++;
        int gdzie=lower_bound(mapka[-S[i]].begin(),mapka[-S[i]].end(),i)-mapka[-S[i]].begin();
        mam[mapka[-S[i]][gdzie]]=1;
        wynik+=ile(i+1,mapka[-S[i]][gdzie]+1)-2;
        usun(i+1);
        usun(mapka[-S[i]][gdzie]+1);
    }
    return wynik;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     while(pot<=S.size())
      |           ~~~^~~~~~~~~~
shoes.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<S.size();i++)
      |                 ~^~~~~~~~~
shoes.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=1;i<=S.size();i++)
      |                 ~^~~~~~~~~~
shoes.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<S.size();i++)
      |                 ~^~~~~~~~~

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