Submission #809158

#	Time	Username	Problem	Language	Result	Execution time	Memory
809158		HoriaHaivas	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	95 ms	136964 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> es;
queue<long long> unassigned[100005];
vector<pair<long long,long long>> perechi;
long long aib[200005];

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

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

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

long long count_swaps(vector<int> S)
{
    long long i;
    es=S;
    for (i=0;i<S.size();i++)
    {
         if (unassigned[abs(S[i])].empty())
             unassigned[abs(S[i])].push(i);
         else if (S[unassigned[abs(S[i])].front()]!=S[i])
         {
             perechi.push_back({unassigned[abs(S[i])].front(),i});
             unassigned[abs(S[i])].pop();
         }
    }
  assert(!((perechi.size()*2)!=S.size()));
    long long ans;
    ans=0;
    sort(perechi.begin(),perechi.end(),cmp);
    for (i=0;i<perechi.size();i++)
    {
         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++;
         update(perechi[i].first+2,1);
         update(perechi[i].second+2,-1);
    }
    return ans;
}

Compilation message (stderr)

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