Cod sursa(job #1971001)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 19 aprilie 2017 19:12:19
Problema NKPerm Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "nkperm.in" , ios::in  );
fstream out( "nkperm.out", ios::out );

const int KMAX = 5;
const int NMAX = 20;
const int NKMAX = 100;

const long long INF = (1LL << 55);

unordered_map<int, long long> mmp;
int pwr[KMAX + 2], frq[NMAX + 1], arr[NKMAX + 1];

inline tuple<int, vector<int>> decrypt( int msk, int n, int k ) {
    int lst = msk / pwr[k + 1];
    
    vector<int> cnt;
    for( int i = 0; i <= k; i ++ )
        cnt.push_back( msk / pwr[i] % (n + 1) );
    
    return tie( lst, cnt );
}

inline int encrypt( int lst, vector<int> cnt, int n, int k ) {
    int msk = lst * pwr[k + 1];
    
    for( int i = 0; i <= k; i ++ )
        msk += pwr[i] * cnt[i];
    
    return msk;
}

long long count( int msk, int n, int k ) {
    if( mmp.find( msk ) != mmp.end() )
        return mmp[msk];
    
    if( msk / pwr[k] % (n + 1) == n )
        mmp[msk] = 1;
    else {
        int lst; vector<int> cnt;
        tie( lst, cnt ) = decrypt( msk, n, k );
        
        long long ans = 0;
        for( int i = 0; i < k; i ++ ) {
            if( cnt[i] == 0 )
                continue;
            
            cnt[i] --; cnt[i + 1] ++;
            ans = min( INF, ans + ( cnt[i] + ( i != lst ) ) *
                       count( encrypt( i + 1, cnt, n, k ), n, k ) );
            cnt[i] ++; cnt[i + 1] --;
        }
        
        mmp[msk] = ans;
    }
    
    return mmp[msk];
}

int main( void ) {
    
    int n, k, t;
    in >> n >> k >> t;
    
    pwr[0] = 1;
    for( int i = 1; i <= k + 1; i ++ )
        pwr[i] = pwr[i - 1] * (n + 1);

    while( t -- ) {
        char ch;
        in >> ch;
        
        vector<int> cnt( k + 1 );
        long long ans = 0; cnt[0] = n;
        
        fill( frq + 1, frq + n + 1, 0 );
        if( ch == 'A' ) {
            for( int i = 1; i <= n * k; i ++ ) {
                in >> arr[i];
                
                for( int j = 1; j < arr[i]; j ++ ) {
                    if( j == arr[i - 1] || frq[j] == k )
                        continue;
                    
                    cnt[frq[j]] --; frq[j] ++; cnt[frq[j]] ++;
                    ans += count( encrypt( frq[j], cnt, n, k ), n, k );
                    cnt[frq[j]] --; frq[j] --; cnt[frq[j]] ++;
                }
                
                cnt[frq[arr[i]]] --; frq[arr[i]] ++; cnt[frq[arr[i]]] ++;
            }
            
            out << ans + 1 << "\n";
        }
        else {
            long long val;
            in >> val;
            
            for( int i = 1, pos = 1; i <= n * k; i ++, pos = 1 ) {
                for( int j = 1; j <= n; j ++, pos = j ) {
                    if( j == arr[i - 1] || frq[j] == k )
                        continue;
                    
                    cnt[frq[j]] --; frq[j] ++; cnt[frq[j]] ++;
                    
                    if( ans +  count( encrypt( frq[j], cnt, n, k ), n, k ) < val )
                        ans += count( encrypt( frq[j], cnt, n, k ), n, k );
                    else
                        break;
    
                    cnt[frq[j]] --; frq[j] --; cnt[frq[j]] ++;
                }
                
                arr[i] = pos; out << arr[i] << " ";
            }
            
            out << "\n";
        }
    }
    
    return 0;
}