Cod sursa(job #2632390)

Utilizator giotoPopescu Ioan gioto Data 3 iulie 2020 10:39:32
Problema NKPerm Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <bits/stdc++.h>
using namespace std;

const long long MAX = 1LL << 55;

int n, k, t;
int freq[25];
vector <int> primes;
map <pair <vector <int>, int>, long long> mem;

long long get_nr(vector <int> freq, int last) {
    if (mem.count({freq, last})) return mem[{freq, last}];

    long long ans = 0;
    for (int i = 0; i < n ; ++i) {
        if (freq[i] && i != last) {
            --freq[i];
            ans = ans + get_nr(freq, i);
            if (ans >= MAX) break ;
            ++freq[i];
        }
    }

    mem[{freq, last}] = ans;
    return ans;
}

int main()
{
    freopen("nkperm.in", "r", stdin);
    freopen("nkperm.out", "w", stdout);

    scanf("%d%d%d\n", &n, &k, &t);

    char tip;
    long long cnt;

    vector <int> freq(n, 0);
    for (int i = 0; i < n ; ++i) mem[{freq, i}] = 1;

    while (t--) {
        scanf("%c", &tip);
        if (tip == 'A') {
            cnt = 0;

            for (int i = 0; i < n ; ++i) freq[i] = k;

            int x, last = -1;
            long long ans = 1;
            for (int i = 1; i <= n * k ; ++i) {
                scanf("%d", &x);
                --x;
                for (int j = 0; j < x ; ++j) {
                    if (freq[j] && j != last) {
                        --freq[j];
                        ans = ans + get_nr(freq, j);
                        ++freq[j];
                    }
                }
                last = x;
                --freq[x];
            }

            printf("%lld", ans);
        }
        else {
            scanf("%lld", &cnt);
            for (int i = 1; i <= n ; ++i) freq[i - 1] = k;

            vector <int> ans(n * k + 1, 0);
            int last = -1;
            for (int i = 1; i <= n * k ; ++i) {
                for (int j = 0; j < n ; ++j) {
                    if (!freq[j] || j == last) continue ;
                    --freq[j];

                    long long aux = get_nr(freq, j);
                    if (cnt <= aux) {
                        last = j;
                        ans[i] = j + 1;
                        break ;
                    }
                    else cnt -= aux, ++freq[j];
                }
            }

            for (int i = 1; i <= n * k ; ++i)
                printf("%d ", ans[i]);
        }

        printf("\n");
        scanf("\n");
    }

    return 0;
}