13. Permutation of Array - solution

Naive Solution 

#include < iostream >
#include < vector >
#include < fstream >
#define DATOTEKA "01.in"

using namespacestd;
void writing(vector& v)
{
//sorting an array using the insertion method
for(vector < int >::iterator it=v.begin(); it != v.end(); ++it)
{
cout<<(*it)<<" ";
}
}
int main()
{
//plugin for reading from a file
/* fstream dataFile;
dataFile.open(DATOTEKA);
if (dataFile.fail())
{
cerr << "Error read data!" << endl;
system("PAUSE");
return 1;
}*/
 int n;
long long m;
cin >> n >> m; //It should be disabled for reading data from the file
// dataFile >> n >> m; //add for reading from a file
vector< int >arr;
vector< int >arr2(n);
vectorshema(n);
for(int i=0; i < n; i++)
{
int a;
cin >> a; //It should be disabled for reading data from the file
// dataFile>>a; //add for reading from a file
arr.push_back(a);
shema[a]=i;
}
// dataFile.close(); //add if file is used to read data
for(int i=1; i < m; i++) //Repeating the permutation of the array, m times
{
vector< int >arr2;
for(int j=0; j < n; j++)
{
int posN = shema[j]; //a new move position is read from the schema
int s=arr[j]; //element to move to a new position
arr2[posN]=s;
}
arr=arr2;
}
writing(arr);
return 0;
}

Solution using the fast scaling algorithm

#include < iostream >
#include < vector >
#include < fstream >
#define DATOTEKA "01.in"

using namespacestd;
void writing(vector& v)
{
//sorting an array using the insertion method
for(vector < int >::iterator it=v.begin(); it != v.end(); ++it)
{
cout<<(*it)<<" ";
}
}
int main()
{
//plugin for reading from a file
/* fstream dataFile;
dataFile.open(DATOTEKA);
if (dataFile.fail())
{
cerr << "Error read data!" << endl;
system("PAUSE");
return 1;
}*/
 int n;
long long m;
cin >> n >> m; //It should be disabled for reading data from the file
// dataFile >> n >> m; //add for reading from a file
vector< int >arr;
vector< int >arr2(n);
vector< int >shema(n);
for(int i=0; i < n; i++)
{
int a;
cin >> a; //It should be disabled for reading data from the file
// dataFile>>a; //add for reading from a file
arr.push_back(a);
shema[a]=i;
}
// dataFile.close(); //add if file is used to read data

if(m == 1)
{
ispisi(arr);
return 0;
}
m=m-1;

while(m >= 1)
{
vectorarr2(n);
for(int j=0; j < n; j++)
{
int posN;
if(m%2 == 1)
{
posN= shema[j];
int s=arr[j];
arr2[posN]=s;
}
else
{
//Transforming shema using shema posN= shema[j];
int s=shema[posN];
arr2[j]=s;
}
}
if(m==1)
{
writing(arr2);
return 0;
}
else if(m%2 == 1)
{
arr=arr2;
m--;
}
else
{
shema=arr2;
// writing(shema);
m/=2;
}
}
writing(arr2);
return 0;
}
Return to the web page Preparation for district competitions