2478 - Find the sequence

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=2478

[ReynaldoGil]

El código debajo lo único que hace es guardar la entrada y calcular todas las permutaciones posibles, y aún así obtiene WA en el caso 2, creo que los jueces deberían chequear los juegos de datos...

Code: Select all

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
using namespace std;
const int MAX=2e2 + 10;
int N, M;
int var[MAX * MAX][4];

int main(){
     scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++){
        int t, x, y, v; scanf("%d%d%d%d", &t, &x, &y, &v);
        x--; y--; v--;
        var[i][0] = t-1; var[i][1] = x; var[i][2] = y; var[i][3] = v;
    }
    int tt[N];
    for(int i = 0 ; i<N; i++)tt[i] = i;
    do{
    	bool right = 1;
    	
    	for(int i=0; i<M; i++)
			if(var[i][0]==0){
				if(*max_element(tt + var[i][1], tt + var[i][2] + 1) != var[i][3]) {
					right = 0;
					break;
				}
			}
			else{
				if(*min_element(tt + var[i][1], tt + var[i][2] + 1) != var[i][3]) {
					right = 0;
					break;
				}
			}
		
    	if(right){
    		for (int i = 0; i < N; i++)
				printf("%d%c", tt[i] + 1 , (i == N - 1 ? '\n' : ' '));
    		return 0;
    	}
    }while(next_permutation(tt, tt+N));
    printf("-1\n");
}

[ymondelo20]

Supongo que solo suerte de imprimir -1, y que el primer dataset coincida.
Es perfectamente posible creo.

[ReynaldoGil]

Acabo de aceptar una solución que no da bien ni para el caso de ejemplo, más bien es la respuesta al problema pero sin l acondición de ser la lexicográficamente menor... Los problemsetter deberían arreglar esto....

[ymondelo20]

Acabo de corregir finalmente el problema.
En lo adelante, cualquier solución válida, es correcta para el Jurado.
He adicionado en checker para validar las soluciones en este sentido, y rejuzgado todos los envíos.

Salu2