Cod sursa(job #2953337)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 11 decembrie 2022 00:50:23
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
ifstream cin("swap.in");
ofstream cout("swap.out");
const int Nmax = 50009;
char s1[Nmax],s2[Nmax];
int v1[Nmax],v2[Nmax];
int aib[Nmax];
int n,m;

void Update(int poz,int val)
{
    for(int i = poz; i<= n; i+= i&-i)
        aib[i] += val;
}
int Query(int poz)
{
    int sum = 0;
    for(int i=poz; i>0; i-=i&-i)
        sum += aib[i];
    return sum;
}
deque<int> v[40];
int main()
{
    cin>>s1>>s2;
    n = strlen(s1),m = strlen(s2);
    for(int i=0;i<n;++i)
    {
        v[s2[i]-'a'].push_back(i+1);
        v2[i+1] = i+1;
    }
    for(int i=0;i<n;++i)
    {
        if(v[s1[i]-'a'].empty())
        {
            cout<<"-1";
            return 0;
        }
        v1[i+1] = v[s1[i]-'a'].front();
        v[s1[i]-'a'].pop_front();
    }
    /// v1 contine permutarea
    int ans = 0;
    for(int i=1;i<=n;++i)
        ans += v1[i] - 1 - Query(v1[i]),
        Update(v1[i],1);
    cout<<ans;
    return 0;
}