Falta uma - F2P2 - OBI 2016

falta.cpp

// Falta uma - F2P2 - OBI 2016
// Rogério Júnior
// Complexidade: O(N!*N*log(N!))

#include "bits/stdc++.h"

using namespace std;

#define PB push_back

set< vector<int> > s;

vector<int> v;

int n, fat=1;

int main(){

	// leio o valor de N
	cin >> n;
	
	// calculo N! para saber quantas permutações estarão na entrada
	for(int i=1;i<=n;i++) fat*=i;
	
	// para cada uma das N!-1 permutações
	for(int i=1;i<fat;i++){
		
		// a guardo no vector u
		vector<int> u;

		for(int j=0;j<n;j++){
			
			// adicionando a ele cada um de seus elementos
			int a;
			cin >> a;

			u.PB(a);
		}
		
		// e adiciono u em um set s
		s.insert(u);
	}
	
	// crio um vector com os números de 1 a N
	for(int i=1;i<=n;i++) v.PB(i);
	
	// e crio um loop
	while(true){
		
		// que só para se v não estiver no set
		if(s.find(v)==s.end()) break;
		
		// e enquanto estiver, transforma v na próxima permutação
		// e continua para a próxima iteração do loop
		next_permutation(v.begin(),v.end());
	}
	
	// quando o loop acabar, v será a permutação que falta
	// então imprimo seus elementos
	for(int i=0;i<v.size();i++) cout << v[i] << " \n"[i==n-1];
	
	// por fim, retorno zero
	return 0;
}

Não é necessário gerar todas as permutações para resolver o problema. Existe uma solução de complexidade menor.
https://gist.github.com/IvanIsCoding/f271ac85b49e0b143b7edb19b79caa15