| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1307769 | lufychop | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(vector<int> s)
{
n=s.size();
long long ans=0;
long long LL=0,RR=n-1;
for(int i=0;i<n;i++)
{
mp[s[i]].push_back(i);
}
while(LL<RR)
{
if(s[LL]!=0)
{
long long tmp=0;
long long L=LL+1;
long long R=mp[-s[LL]].front();
mp[s[LL]].pop_front();
mp[-s[LL]].pop_front();
for(int i=L;i<=R;i++)
{
if(s[i]==0)
{
tmp++;
}
}
ans=ans+R-LL-1-tmp;
// cout<<LL<<R<<"\n";
if(s[R]<0)
{
ans++;
}
s[R]=0;
s[LL]=0;
}
if(s[RR]!=0)
{
long long tmp=0;
long long L=mp[-s[RR]].back();
long long R=RR-1;
mp[-s[RR]].pop_back();
mp[s[RR]].pop_back();
for(int i=L;i<=R;i++)
{
if(s[i]==0)
{
tmp++;
}
}
ans=ans+RR-L-1-tmp;
// cout<<L<<RR<<"\n";
if(s[L]>0)
{
ans++;
}
s[L]=0;
s[RR]=0;
}
// cout<<LL<<RR;
LL++;
RR--;
}
return ans;
}
