Untitled
unknown
plain_text
a year ago
2.7 kB
3
Indexable
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> bool isBeautiful(long long int arr[], long long int n) { if (n < 3) return true; for (long long int i = 0; i < n - 2; i++) { long long int diff1 = arr[i + 1] - arr[i]; long long int diff2 = arr[i + 2] - arr[i + 1]; if ((diff1 >= 0 && diff2 >= 0) || (diff1 <= 0 && diff2 <= 0)) return false; } return true; } void generatePermutations(long long int arr[], long long int n, long long int used[], long long int index, long long int ***perms, long long int *count, long long int *capacity) { if (index == n) { // Found a beautiful permutation if (*count == *capacity) { *capacity *= 2; *perms = realloc(*perms, (*capacity) * sizeof(long long int *)); } (*perms)[*count] = malloc(n * sizeof(long long int)); for (long long int i = 0; i < n; i++) { (*perms)[*count][i] = used[i]; } (*count)++; return; } for (long long int i = 0; i < n; i++) { bool alreadyUsed = false; for (long long int j = 0; j < index; j++) { if (used[j] == arr[i]) { alreadyUsed = true; break; } } if (!alreadyUsed) { used[index] = arr[i]; if (isBeautiful(used, index + 1)) { generatePermutations(arr, n, used, index + 1, perms, count, capacity); } // No need to explicitly backtrack as used[index] will be overwritten in the next iteration } } } int compare(const void *a, const void *b) { long long int *arr1 = *(long long int**)a; long long int *arr2 = *(long long int**)b; long long int n = 0; while (arr1[n] == arr2[n]) n++; return arr1[n] - arr2[n]; } int main() { long long int N; scanf("%lld", &N); long long int arr[N], used[N]; for (long long int i = 0; i < N; i++) { scanf("%lld", &arr[i]); used[i] = 0; } long long int initialCapacity = 1; long long int **beautifulPerms = malloc(initialCapacity * sizeof(long long int *)); long long int count = 0; generatePermutations(arr, N, used, 0, &beautifulPerms, &count, &initialCapacity); qsort(beautifulPerms, count, sizeof(long long int *), compare); printf("%lld\n", count); for (long long int i = 0; i < count; i++) { for (long long int j = 0; j < N; j++) { printf("%lld ", beautifulPerms[i][j]); } printf("\n"); free(beautifulPerms[i]); } free(beautifulPerms); return 0; }
Editor is loading...
Leave a Comment