제출 #809162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809162		HoriaHaivas	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	88 ms	74456 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();
         }
         else
         unassigned[abs(S[i])].push(i);
    }
    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;
}

컴파일 시 표준 에러 (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:63: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]
   63 |     for (i=0;i<perechi.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