UVa : 11925 (Generating Permutations)



// 1. There is always a solution <= 2 * n^2 operations 

// 2. keep continuing operation 2 (moving 1st number at last) unless you need to flip
// there is no harm for some extra operation, though total_operation_count <= 2 * n ^ 2
// for example, initial_permutation, 1 2 3 4 
// target_permutation, 4 2 3 1 
// here, number 2 comes after 4. but initially, 2 comes before 4. so 
// now you want number 2 @position 0 and number 4 @position 1, thus you can flip!
// 1 2 3 4 
// 2 3 4 1
// 3 2 4 1
// 2 4 1 3 
// 4 2 1 3 -- we came down here just for flip 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;


int main ()
{
	int n;

	while ( scanf ("%d", &n) && n ) {

		vector <int> targetPerm;
		int inp;

		for ( int i = 0; i < n; i++ ) {
			scanf ("%d", &inp);
			targetPerm.push_back(inp);
		}

		vector <int> initPerm;
		int tmp;

		for ( int i = 1; i <= n; i++ ) initPerm.push_back(i);

		for ( int i = 1; i < n; i++ ) {

			while ( initPerm [0] != targetPerm [i] ) {
				initPerm.push_back(initPerm [0]);
				initPerm.erase(initPerm.begin());
				printf ("2");
			}

			while ( initPerm [1] != targetPerm [i - 1]) {
				swap (initPerm [0], initPerm [1]);
				printf ("1");
				initPerm.push_back(initPerm [0]);
				initPerm.erase(initPerm.begin());
				printf ("2");
			}

			swap (initPerm [0], initPerm [1]);
			printf ("1");
			initPerm.push_back(initPerm [0]);
			initPerm.erase(initPerm.begin());
			printf ("2");
		}

		bool change = true;

		while ( change ) {
			change = false;
			Fs(i, initPerm) {
				if ( initPerm [i] != targetPerm [i] ) {
					initPerm.push_back(initPerm [0]);
					initPerm.erase(initPerm.begin());
					printf ("2");
					change = true; 
					break;
				}
			}
		}

		//printf ("-");
		//Fs (i, initPerm) printf ("%d ", initPerm [i]); 

		printf ("\n");
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s