Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- int T,n,l;
- ll m;
- struct Trie
- {
- Trie* next[13];
- ll v;
- Trie(){v=-1;memset(next,0,sizeof(next));}
- };
- ll find(Trie* root, vector<int>&lis)
- {
- int i;
- for(i=0;i<(int)lis.size();i++)
- {
- if( !root->next[ lis[i] ] )return -1;
- root=root->next[ lis[i] ];
- }
- return root->v;
- }
- ll assign( Trie* root,vector<int>&lis,ll v )
- {
- int i;
- for(i=0;i<(int)lis.size();i++)
- {
- if( !root->next[ lis[i] ] )root->next[ lis[i] ]=new Trie();
- root=root->next[ lis[i] ];
- }
- root->v=v;
- return v;
- }
- Trie *dp[ (1<<13)+2 ];
- map< vector<int> , ll > :: iterator it;
- void update( vector<int>&lis,int v )
- {
- if( !(int)lis.size() || lis.back()<v )
- {
- lis.push_back(v);
- return;
- }
- for(int i=0;i<lis.size();i++ )
- {
- if( lis[i]>=v )
- {
- lis[i]=v;
- return;
- }
- }
- return;
- }
- ll go( int mask,vector<int>lis,int pos )
- {
- //cout<<mask<<" "<<lis.size()<<endl;
- ll it=find( dp[mask],lis );
- if( it!=-1 )return it;
- if( pos==n )return assign(dp[mask],lis,1);
- int i,nmask;
- vector<int>tlis;
- ll ret=0;
- for( i=0;i<n;i++ )
- {
- if( mask & (1<<i) )continue;
- nmask=mask | (1<<i);
- tlis=lis;
- update(tlis,i);
- if((int)tlis.size()>l)break;
- ret+=go( nmask,tlis,pos+1 );
- }
- return assign(dp[mask],lis,ret);
- }
- int main()
- {
- freopen("in.txt","r",stdin);
- int i,j,k;
- cin>>T;
- //cout<<T<<endl;
- for( int cs=1;cs<=T;cs++ )
- {
- cin>>n>>l>>m;
- // cout<<n<<" "<<l<<" "<<m<<endl;
- for( i=0;i<(1<<n);i++ )
- {
- dp[i]=new Trie();
- }
- printf("Case %d:",cs);
- int mask=0,tmask;
- vector<int>lis,tlis;
- vector<int>res;
- for( i=0;i<n;i++ )
- {
- for(j=0;j<n;j++)
- {
- if( mask & (1<<j) )continue;
- tmask=mask;
- tlis=lis;
- tmask|=( 1<<j );
- update( tlis,j );
- if( (int)tlis.size()>l )break;
- ll v=go( tmask,tlis,i+1 );
- // cout<<v<<" "<<m<<endl;//while(1);
- if( v<m )m-=v;
- else
- {
- // cout<<j<<"**"<<endl;
- res.push_back( j );
- mask=tmask;
- lis=tlis;
- break;
- }
- }
- if( j==n )
- {
- cout<<" -1"<<endl;
- goto hell;
- }
- }
- for( i=0;i<n;i++ )
- {
- printf(" %d",res[i]+1);
- }
- cout<<endl;
- hell:;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement