Advertisement
kaysar

Untitled

Oct 31st, 2014
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int T,n,l;
  5. ll m;
  6.  
  7. struct Trie
  8. {
  9.     Trie* next[13];
  10.     ll v;
  11.     Trie(){v=-1;memset(next,0,sizeof(next));}
  12.  
  13. };
  14.  
  15. ll find(Trie* root, vector<int>&lis)
  16. {
  17.     int i;
  18.     for(i=0;i<(int)lis.size();i++)
  19.     {
  20.         if( !root->next[ lis[i] ] )return -1;
  21.         root=root->next[ lis[i] ];
  22.     }
  23.     return root->v;
  24. }
  25.  
  26. ll assign( Trie* root,vector<int>&lis,ll v )
  27. {
  28.     int i;
  29.     for(i=0;i<(int)lis.size();i++)
  30.     {
  31.         if( !root->next[ lis[i] ] )root->next[ lis[i] ]=new Trie();
  32.         root=root->next[ lis[i] ];
  33.     }
  34.     root->v=v;
  35.     return v;
  36. }
  37.  
  38. Trie *dp[ (1<<13)+2 ];
  39. map< vector<int> , ll > :: iterator it;
  40.  
  41.  
  42. void update( vector<int>&lis,int v )
  43. {
  44.     if( !(int)lis.size() || lis.back()<v )
  45.     {
  46.         lis.push_back(v);
  47.         return;
  48.     }
  49.  
  50.     for(int i=0;i<lis.size();i++ )
  51.     {
  52.         if( lis[i]>=v )
  53.         {
  54.             lis[i]=v;
  55.             return;
  56.         }
  57.     }
  58.  
  59.     return;
  60.  
  61. }
  62.  
  63. ll go( int mask,vector<int>lis,int pos )
  64. {
  65.  
  66.     //cout<<mask<<" "<<lis.size()<<endl;
  67.  
  68.     ll it=find( dp[mask],lis );
  69.     if( it!=-1 )return it;
  70.     if( pos==n )return assign(dp[mask],lis,1);
  71.     int i,nmask;
  72.     vector<int>tlis;
  73.     ll ret=0;
  74.     for( i=0;i<n;i++ )
  75.     {
  76.         if( mask & (1<<i) )continue;
  77.         nmask=mask | (1<<i);
  78.         tlis=lis;
  79.         update(tlis,i);
  80.         if((int)tlis.size()>l)break;
  81.         ret+=go( nmask,tlis,pos+1 );
  82.     }
  83.     return assign(dp[mask],lis,ret);
  84. }
  85.  
  86. int main()
  87. {
  88.  
  89.     freopen("in.txt","r",stdin);
  90.  
  91.     int i,j,k;
  92.     cin>>T;
  93.     //cout<<T<<endl;
  94.  
  95.     for( int cs=1;cs<=T;cs++ )
  96.     {
  97.         cin>>n>>l>>m;
  98.  
  99.       //  cout<<n<<" "<<l<<" "<<m<<endl;
  100.  
  101.  
  102.         for( i=0;i<(1<<n);i++ )
  103.         {
  104.             dp[i]=new Trie();
  105.         }
  106.  
  107.         printf("Case %d:",cs);
  108.  
  109.         int mask=0,tmask;
  110.         vector<int>lis,tlis;
  111.         vector<int>res;
  112.         for( i=0;i<n;i++ )
  113.         {
  114.  
  115.             for(j=0;j<n;j++)
  116.             {
  117.                 if( mask & (1<<j) )continue;
  118.                 tmask=mask;
  119.                 tlis=lis;
  120.  
  121.  
  122.  
  123.                 tmask|=( 1<<j );
  124.                 update( tlis,j );
  125.  
  126.                 if( (int)tlis.size()>l )break;
  127.  
  128.                 ll v=go( tmask,tlis,i+1 );
  129.  
  130.                // cout<<v<<" "<<m<<endl;//while(1);
  131.  
  132.  
  133.                 if( v<m )m-=v;
  134.                 else
  135.                 {
  136.                    // cout<<j<<"**"<<endl;
  137.                     res.push_back( j );
  138.                     mask=tmask;
  139.                     lis=tlis;
  140.                     break;
  141.                 }
  142.             }
  143.  
  144.             if( j==n )
  145.             {
  146.                 cout<<" -1"<<endl;
  147.                 goto hell;
  148.             }
  149.  
  150.  
  151.  
  152.         }
  153.  
  154.  
  155.         for( i=0;i<n;i++ )
  156.         {
  157.             printf(" %d",res[i]+1);
  158.         }
  159.         cout<<endl;
  160.  
  161.  
  162.         hell:;
  163.  
  164.     }
  165.  
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement