//PRZEMYSL ASSERTY //SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE //MODULO = 1 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define FORD(i,a,b) for(int i=(a);i>=(b);--i) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define e1 first #define e2 second #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll inf=2e18; int n,x[250001],zajete[25],ts[1<<19]; ll k; vector<ll> t[250001]; ll mahon(int n,ll k) { ll perm=(ll)n*(n-1)/2; if (k<0 || k>perm) return 0; if (k<(ll)t[n].size()) return t[n][k]; if (perm-k<(ll)t[n].size()) return t[n][perm-k]; return inf; } void dodaj(int a,int x) { a+=1<<18; while (a) ts[a]+=x,a>>=1; } int znajdz(int a) { int nr=1; while (nr<(1<<18)) { nr<<=1; if (ts[nr]<a) a-=ts[nr++]; } return nr-(1<<18); } int main() { scanf("%d%lld",&n,&k); if (n%4>1) puts("NIE"),exit(0); t[1].push_back(1); FOR(i,2,n) { FOR(j,0,(ll)i*(i-1)/2) { ll x=mahon(i-1,j)+mahon(i,j-1)-mahon(i-1,j-i); if (x<=1e18) t[i].push_back(x); else break; } } ll inv=(ll)n*(n-1)/4,pn=n; if (mahon(n,inv)<k) puts("NIE"),exit(0); while (pn>1) { for (ll i=min(inv,(ll)(pn-1)*(pn-2)/2); inv-i<pn; i--) { if (mahon(pn-1,i)<k) k-=mahon(pn-1,i); else { x[n-pn+1]=inv-i; inv=i; break; } } pn--; } puts("TAK"); FOR(i,1,n) dodaj(i,1); FOR(i,1,n) { int p=znajdz(x[i]+1); dodaj(p,-1); printf("%d ",p); } }
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 | //PRZEMYSL ASSERTY //SPRAWDZ CORNER CASE'Y, MINIMALNE I MAKSYMALNE WEJŚCIE I WYJŚCIE //MODULO = 1 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define FORD(i,a,b) for(int i=(a);i>=(b);--i) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define e1 first #define e2 second #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll inf=2e18; int n,x[250001],zajete[25],ts[1<<19]; ll k; vector<ll> t[250001]; ll mahon(int n,ll k) { ll perm=(ll)n*(n-1)/2; if (k<0 || k>perm) return 0; if (k<(ll)t[n].size()) return t[n][k]; if (perm-k<(ll)t[n].size()) return t[n][perm-k]; return inf; } void dodaj(int a,int x) { a+=1<<18; while (a) ts[a]+=x,a>>=1; } int znajdz(int a) { int nr=1; while (nr<(1<<18)) { nr<<=1; if (ts[nr]<a) a-=ts[nr++]; } return nr-(1<<18); } int main() { scanf("%d%lld",&n,&k); if (n%4>1) puts("NIE"),exit(0); t[1].push_back(1); FOR(i,2,n) { FOR(j,0,(ll)i*(i-1)/2) { ll x=mahon(i-1,j)+mahon(i,j-1)-mahon(i-1,j-i); if (x<=1e18) t[i].push_back(x); else break; } } ll inv=(ll)n*(n-1)/4,pn=n; if (mahon(n,inv)<k) puts("NIE"),exit(0); while (pn>1) { for (ll i=min(inv,(ll)(pn-1)*(pn-2)/2); inv-i<pn; i--) { if (mahon(pn-1,i)<k) k-=mahon(pn-1,i); else { x[n-pn+1]=inv-i; inv=i; break; } } pn--; } puts("TAK"); FOR(i,1,n) dodaj(i,1); FOR(i,1,n) { int p=znajdz(x[i]+1); dodaj(p,-1); printf("%d ",p); } } |