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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAX_N 250000
int a[MAX_N], b[MAX_N], pom[MAX_N];	
long long merge(int *a, int *b, int p, int q,	int r);				
/* b to tablica pomocnicza dla procedury merge	*/	
long long mergesort(int *a, int *b, int p, int	r);
int tab[250000];

int main()
{
int n, i, j,liczba_inwersji;
long long wyn=0, wyn1=0,wyn2=0,k;
scanf("%d%lld",&n,&k);
if(n < 14) {
for(j = 0; j < n; ++j) {
	tab[j] = j;
}
while(next_permutation(tab,tab+n)){
	for(j = 0; j < n; ++j) {
		a[j] = tab[j];
		pom[j] = tab[n- j - 1];
	}		
	//for(j = 0; j < n; ++j) printf("%d ",a[j]+1); 
	wyn1 = mergesort(a, b, 0, n - 1);	
	//printf("%lld ", wyn1);	printf("\n");	
	//for(j = 0; j < n; ++j) printf("%d ",a[j]+1); 
	wyn2 = mergesort(pom, b, 0, n - 1);	
	//printf("%lld ", wyn2);printf("\n");
	if(wyn1==wyn2) wyn++;
	if(wyn==k) break;
}
if(wyn < k) printf("NIE\n");
else {
	printf("TAK\n");
	for(j = 0; j < n; ++j) printf("%d ",tab[j]+1); 
}
}
else{
	if(n % 4==0) liczba_inwersji = n/4 *(n-1);
	else if(n%4 == 1) liczba_inwersji = n/4 * n;
	printf("NIE\n");
}
return 0;
}
					
							
long long merge(int *a, int *b, int p, int q,	int r)				
{					
/* Procedura scalajaca dwa posortowane ciagi	a[p..q] z	a[	q+	1..r] przy *	
* wykorzystaniu tablicy pomocniczej b, a ko	nkretniej	jej	f	ragmentu   *	
* b[p..r].				*/	
int i = p;					
int j = q + 1;					
int s = p;					
long long wyn = 0, ile_druga = 0;					
while (i <= q && j <= r)					
{					
if (a[i] <= a[j]) /* Wazne, zeby tu bylo d	obre porow	nan	ie	*/	
{					
b[s] = a[i];					
i++;					
wyn += ile_druga; /* Ile juz wrzucilismy	z drugiej	po	lo	wki? */	
}					
else					
{					
b[s] = a[j];					
j++;					
ile_druga++;					
}					
s++;					
}					
/* Skonczyl sie ktorys z ciagow: a[p..q] lub	a[q+1..r]	. N	al	ezy ogon *	
* drugiego ciagu przepisac do tablicy b na	pozycje s+	1..	r.	*/	
while (i <= q)					
{					
b[s] = a[i];					
i++;					
s++;					
wyn += ile_druga; /* Ile juz wrzucilismy z	drugiej p	olo	wk	i? */	
}					
while (j <= r)					
{					
b[s] = a[j];					
j++;					
s++;					
}					
					
/* Teraz pozostaje tylko przepisac wynik-pos	ortowany c	iag	z	tablicy  *	
* do tablicy a				*/	
for (int it = p; it <= r; it++)					
a[it] = b[it];					
return wyn;					
}					
					
long long mergesort(int *a, int *b, int p, int	r)				
{					
long long wyn = 0LL;					
if (p == r) return wyn;					
int q = (p + r)/2;					
/* Sumujemy liczby inwersji z obu polowek */					
wyn += mergesort(a, b, p, q);					
wyn += mergesort(a, b, q + 1, r);					
/* I liczbe inwersji miedzypolowkowych */					
wyn += merge(a, b, p, q, r);					
return wyn;					
}