#include "permutation.h"
#include <iostream>
#include <vector>
using namespace std;
vector<int> decode(vector<int> a) {
	vector<bool> used(a.size()+1, 0);
	int ptr = 1;
	for(int i = 0; i < a.size(); i++) {
		if(ptr > a.size()) return {0};
		if(a[i]==-1) {
			a[i]=ptr;
			used[ptr]=1;
		}
		else {
			used[a[i]]=1;
		}
		while(used[ptr] && ptr <= a.size()) ptr++; 
	}
	return a;
}

vector<int> encode(vector<int> a) {
	int mx = 0;
	vector<int> best=a;
	for(int i = 0; i < (1<<a.size()); i++) { // bitmask
		string s = "";
		int tmp = i;
		while(tmp) {
			s.push_back((char)(tmp%2+'0'));
			tmp/=2;
		}
		while(s.size()<a.size()) s.push_back('0');
		vector<int> curr = a;
		int currcnt=0;
		for(int j = 0; j < a.size(); j++) {
			if(s[j]=='1') { // put -1
				curr[j]=-1;
				currcnt++;	
			}
		}
		vector<int> decoded = decode(curr);
		if(decoded[0]==0) continue;
		if(decoded != a) continue;
		if(currcnt > mx) {
			mx = currcnt;
			best = curr;
		}
	}
	return best;
}

