Cod sursa(job #1514024)

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

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(fr[i])
        {
            int t=(i-1)*rad;
            for(;t<i*rad;t++)
            {
                if(x[t]!=z[t])
                {
                    int c=x[t];
                    swp(x[y[0]],x[t]);
                    swp(y[0],y[c]);
                    nr++;
                    ok=1;
                    i=k+1;
                    t=i*rad;
                }
            }
        }
    }
}
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;
    s=sqrt(n);
    rad=s;
    for(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;
}