Submission #529577

#	Time	Username	Problem	Language	Result	Execution time	Memory
529577		groshi	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	342 ms	33320 KiB

shoes

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
map<int,set<int> > mapka;
int pot=1;
int drzewo[800000];
bool mam[400000];
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]].insert(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++;
        auto it=mapka[-S[i]].begin();
        int gdzie=*it;
        mapka[-S[i]].erase(it);
        mam[gdzie]=1;
        wynik+=ile(i+1,gdzie+1)-2;
        usun(i+1);
        usun(gdzie+1);
        it=mapka[S[i]].begin();
        mapka[S[i]].erase(it);
    }
    return wynik;
}

Compilation message (stderr)

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

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