13. Permutation of Array - solution
Naive Solution
#include < iostream >
#include < vector >
#include < fstream >
#define DATOTEKA "01.in"
using namespace std;
void writing(vector& v)
{
int main()
{
#include < vector >
#include < fstream >
#define DATOTEKA "01.in"
using namespace std;
void writing(vector
{
//sorting an array using the insertion method
for(vector < int >::iterator it=v.begin(); it != v.end(); ++it)
{
}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())
{
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++)
{
// 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
{
writing(arr);
return 0;
}
/* fstream dataFile;
dataFile.open(DATOTEKA);
if (dataFile.fail())
{
cerr << "Error read data!" << endl;
system("PAUSE");
return 1;
}*/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
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;
}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++)
arr=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;
}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 namespace std;
void writing(vector& v)
{
int main()
{
#include < vector >
#include < fstream >
#define DATOTEKA "01.in"
using namespace std;
void writing(vector
{
//sorting an array using the insertion method
for(vector < int >::iterator it=v.begin(); it != v.end(); ++it)
{
}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())
{
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++)
{
// dataFile.close(); //add if file is used to read data
if(m == 1)
{
m=m-1;
while(m >= 1)
{
writing(arr2);
return 0;
}
/* fstream dataFile;
dataFile.open(DATOTEKA);
if (dataFile.fail())
{
cerr << "Error read data!" << endl;
system("PAUSE");
return 1;
}*/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;
}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;
}return 0;
m=m-1;
while(m >= 1)
{
vectorarr2(n);
for(int j=0; j < n; j++)
{
if(m==1)
{
else if(m%2 == 1)
{
else
{
}for(int j=0; j < n; j++)
{
int posN;
if(m%2 == 1)
{
else
{
}if(m%2 == 1)
{
posN= shema[j];
int s=arr[j];
arr2[posN]=s;
}int s=arr[j];
arr2[posN]=s;
else
{
//Transforming shema using shema
posN= shema[j];
int s=shema[posN];
arr2[j]=s;
}int s=shema[posN];
arr2[j]=s;
if(m==1)
{
writing(arr2);
return 0;
}return 0;
else if(m%2 == 1)
{
arr=arr2;
m--;
}m--;
else
{
shema=arr2;
// writing(shema);
m/=2;
}// writing(shema);
m/=2;
writing(arr2);
return 0;
Return to the web page Preparation for district competitions