Cod sursa(job #1513995)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 30 octombrie 2015 14:01:07
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <cmath>
#define D 100010
using namespace std;
ifstream f("album.in");
ofstream g("album.out");
int n,nr,nrm,ok=1;
int x[D],y[D],z[D],fr[400];

void swp(int &a, int &b)
{
    int aux=a;
    a=b;
    b=aux;
}

void urm()
{
    ok=0;
    for(int i=1;i<=k;++i)
    {
        if(x[i]!=z[i])
        {
            int c=x[i];
            swp(x[y[0]],x[i]);
            swp(y[0],y[c]);
            nr++;
            ok=1;
        }
    }
}
int main()
{   f>>n;
    int i;
    for(i=0;i<n;++i)
    {
        f>>x[i];
        y[x[i]]=i;
    } //x=sirul initial, y=inversa
    for(i=0;i<n;++i) f>>z[i]; //z=sirul final

    i=0;
    int rad=sqrt(n);
    for(int k=1;i<n;++k)
    {
        for(int j=0;j<rad;++j,++i)
        {
            if(x[i]!=z[i])
            {
                fr[k]++;
            }
        }
    }

    while(ok)
    {

        if(x[y[0]]==z[y[0]]) urm();
        else
        {
            int c=x[y[z[y[0]]]];
            swp(x[y[z[y[0]]]],x[y[0]]);

            swp(y[0],y[c]);
            nr++;
        }
    }
    g<<nr;
    g.close();f.close();
    return 0;
}