Submission #807653

#	Time	Username	Problem	Language	Result	Execution time	Memory
807653		HoriaHaivas	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	2 ms	2652 KiB

shoes

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

vector<int> S;
vector<int> unassigned[100005];
vector<pair<int,int>> perechi;
int aib[200005];

void update(int index, int delta)
{
     while (index<=S.size())
     {
         aib[index]+=delta;
         index+=index&(-index);
     }
}

int query(int index)
{
    int ans;
    ans=0;
    while (index>0)
    {
        ans+=aib[index];
        index-=index&(-index);
    }
    return ans;
}

bool cmp(pair<int,int> a, pair<int,int> b)
{
    return a.first<b.first;
}

long long count_swaps(vector<int> S)
{
    int i;
    for (i=0;i<S.size();i++)
    {
         if (unassigned[abs(S[i])].size()==0)
             unassigned[abs(S[i])].push_back(i);
         else if (S[unassigned[abs(S[i])][0]]!=S[i])
         {
             perechi.push_back({unassigned[abs(S[i])][0],i});
             unassigned[abs(S[i])].pop_back();
         }
    }
    int ans;
    ans=0;
    sort(perechi.begin(),perechi.end(),cmp);
    for (i=0;i<perechi.size();i++)
    {
         update(perechi[i].first+1,1);
         update(perechi[i].second+2,-1);
         ans+=(perechi[i].second-perechi[i].first-1)-(abs(query(perechi[i].first+1)-query(perechi[i].second+1)));
         if (S[perechi[i].second]<S[perechi[i].first])
             ans++;
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void update(int, int)':
shoes.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |      while (index<=S.size())
      |             ~~~~~^~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (i=0;i<S.size();i++)
      |              ~^~~~~~~~~
shoes.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (i=0;i<perechi.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