1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 #include #include #include int tmp[250002]; int merge(int t[],int p, int m, int r,int n){ for (int i = p; i <= r; i++) tmp[i] = t[i]; int i = p; int j = m + 1; int k = p; int result = 0; int howManyWrong = 0; while (i <= m && j <= r){ if (tmp[i] <= tmp[j]){ t[k++] = tmp[i++]; result += howManyWrong; } else{ t[k++] = tmp[j++]; howManyWrong++; } } while (i <= m){ t[k++] = tmp[i++]; result += howManyWrong; } while (j <= r){ t[k++] = tmp[j++]; } return result; } int mergesort(int t[],int p, int r,int n){ int result = 0; if (p >= r) return 0; int m = (p + r)/2; result += mergesort(t, p, m,n); result += mergesort(t, m + 1, r,n); return merge(t, p, m, r,n) + result; } int liczba_inwersji(int* tab, int n,bool rev) { int input[n]; if(!rev) for(int i = 0;i < n;i++) input[i] = tab[i]; else for(int i = 0;i < n;i++) input[i] = tab[n-i-1]; return mergesort(input,0,n-1,n); } int main(){ int n,k; scanf("%d %d",&n,&k); long long int maxInv = (n*(n-1))/2; if(n == 1 || n == 2 || maxInv%2) printf("NIE\n"); else{ int tab[n]; for(int i = 0;i < n;i++){ tab[i] = i; } int number = 0; bool dowhile = true; while(dowhile && number != k){ dowhile = std::next_permutation(tab,tab+n); int inversion = liczba_inwersji(tab,n,false); int inversionRev = liczba_inwersji(tab,n,true); if(inversion == inversionRev){ number++; } } if(number != k) printf("NIE\n"); else { printf("TAK\n"); for(int i = 0;i < n;i++){ printf("%d ",tab[i] + 1); } printf("\n"); } } } //Author: Helena Borak