Overview

Since the encryption conversion rule \(C\) changes depending on the transmission order, the “original password \(S\) required for success” for each agent varies depending on the order.
However, since \(N \le 8\) is small, we can enumerate all transmission orders, compute the maximum number of successes achievable and the lexicographically smallest \(S\) for each order, and finally select the overall optimum.

Analysis

The key observation is as follows:

• When a transmission order is fixed, the conversion rule \(C\) at each step is determined.
• The condition for agent \(i\) to succeed at that point is $\( (C_{S_1},\dots,C_{S_L}) = T_i \)\( so for each position \)j\(, \)\( S_j = C^{-1}(T_{i,j}) \)\( is required. In other words, the \)S\( needed for that agent's success is determined as **one complete pattern** of length \)L$.

For a fixed order:

• At each transmission step \(p\), a “success pattern” \(P_p\) is formed.
• Since only one \(S\) is chosen, the agents that succeed are the group of agents whose \(P_p\) exactly matches \(S\).
• Therefore, the maximum number of successes for that order is
  “the maximum occurrence count of identical patterns among those that are compatible with \(B\) (no contradiction with fixed characters).”

A naive approach of using state DP over “which subset of agents to make succeed” makes consistency per position and order-dependence complex and difficult to implement.
Since this solution uses exhaustive search over all \(N!\) orderings (at most \(8!=40320\)), it is sufficiently fast and safer.

Algorithm

1. Convert input to 0-indexed (value range \(0..K-1\), convert \(B_j=0\) to \(-1\)).
2. Enumerate all permutations of agents.
3. For each permutation:
   • Initialize conversion \(C\) as the identity permutation.
   • Process agents in order:
     • Compute the inverse mapping \(\mathrm{inv}\) of the current \(C\).
     • Construct the required pattern for that agent as
       \(P_p[j]=\mathrm{inv}[T_{i,j}]\).
     • Update after transmission: \(C \leftarrow A_i \circ C\) (in code: newC[x] = A[i][C[x]]).
   • For the \(N\) obtained patterns \(P_p\):
     • Only those not contradicting \(B\) are candidates.
     • Count occurrences of identical patterns and obtain the maximum localBest.
     • If there are ties, adopt the lexicographically smallest pattern.
   • If there are no candidates, the number of successes is 0.
     In this case, the lexicographically smallest valid \(S\) is “fill in 0 (=value 1) where \(B_j\) is undetermined.”
4. Compare results across all permutations and select:
   • Maximum number of successes
   • If tied, the lexicographically smallest \(S\) as the final answer.
5. Convert back to 1-indexed and output.

Complexity

• Time complexity: \(O(N! \cdot N \cdot (K + L) + N! \cdot N^2 \cdot L)\)
  Effectively \(O(N! \cdot N^2 \cdot L)\) (sufficiently fast since \(N \le 8\))
• Space complexity: \(O(N \cdot L + K)\) (including working space per permutation)

Implementation Notes

• Pay attention to the direction of permutation composition: the update is \(C' = A_i \circ C\).

• The success condition is \(S_j = C^{-1}(T_{i,j})\), so it is easiest to compute the inverse mapping at each step.

• Lexicographic comparison can be conveniently done using comparison of vector<int> (C++’s lexicographic comparison).

• Even when the number of successes is 0, the problem requires the lexicographically smallest feasible \(S\), so this case must always be handled.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, L;
    cin >> N >> K >> L;

    vector<int> B(L);
    for (int j = 0; j < L; j++) {
        cin >> B[j];
        --B[j]; // 0->-1, 1..K -> 0..K-1
    }

    vector<vector<int>> T(N, vector<int>(L));
    vector<vector<int>> A(N, vector<int>(K));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < L; j++) {
            cin >> T[i][j];
            --T[i][j];
        }
        for (int x = 0; x < K; x++) {
            cin >> A[i][x];
            --A[i][x];
        }
    }

    int ALL = 1 << N;

    // precompute composed permutation for each subset mask in "send order":
    // starting C = id, for each bit i in ascending index if in mask, C = A_i o C
    vector<array<int,8>> Cmask(ALL);
    for (int m = 0; m < ALL; m++) {
        for (int x = 0; x < K; x++) Cmask[m][x] = x;
    }
    for (int m = 1; m < ALL; m++) {
        int b = __builtin_ctz(m);
        int pm = m ^ (1 << b);
        for (int x = 0; x < K; x++) {
            Cmask[m][x] = A[b][ Cmask[pm][x] ];
        }
    }

    // need[mask][i][v] : for state mask (already sent set), if send i next, then S_j must be v
    // v in 0..K-1, or -1 impossible
    static int8_t need[1<<8][8][8];
    for (int mask = 0; mask < ALL; mask++) {
        for (int i = 0; i < N; i++) {
            for (int v = 0; v < K; v++) need[mask][i][v] = -1;
            if (mask & (1 << i)) continue;
            // inverse of Cmask[mask]
            int inv[8];
            for (int x = 0; x < K; x++) inv[Cmask[mask][x]] = x;
            for (int t = 0; t < K; t++) {
                need[mask][i][t] = (int8_t)inv[t];
            }
        }
    }

    // good[mask][j]: among agents in mask, all required S_j equal and compatible with B_j
    vector<vector<char>> good(ALL, vector<char>(L, 1));
    for (int mask = 0; mask < ALL; mask++) {
        for (int j = 0; j < L; j++) {
            int val = -2; // unset
            bool ok = true;
            for (int i = 0; i < N; i++) if (mask & (1 << i)) {
                int req = need[mask ^ (1 << i)][i][ T[i][j] ]; // careful? actually state before sending i within topological?
                // Not valid like this. For mask-only feasibility, requirement depends on prefix state, not just final set.
                // So we cannot do this precompute this way.
            }
        }
    }

    // We'll do DP over sequences with constraints aggregated incrementally.
    // For each mask, keep:
    // dp[mask] = max successes achievable by some order consisting exactly of mask agents (success counted within those sends),
    // and for each position j, required value req[mask][j] if that best is achievable; but multiple possibilities.
    // Need lexicographic minimal S among global optimum -> handle via two-phase:
    // 1) compute best possible success count with DP feasibility per mask and position constraints as bitsets.
    //    For each mask, we keep all possible "requirement patterns"? too huge.
    // Alternative: since N<=8, brute force all orders (40320) and for each derive feasible S and success count.
    // For each order, success set determined by S; but S can be chosen to maximize successes in that fixed order.
    // For fixed order, each agent at step p imposes for each j a value r_{p,j} = inv(C_before)(T_i[j]).
    // Need choose S_j (respecting B) to maximize count of p such that all j match r_{p,j}.
    // That means each agent corresponds to full length pattern R_p[1..L]. Agent succeeds iff S equals that pattern exactly.
    // So with one S, in a fixed order, successful agents are those p whose pattern equals S.
    // Therefore max success in that order is max frequency of an identical feasible pattern among agents in that order,
    // but pattern itself independent of order position via C_before so depends on prefix.
    // N small => for each permutation, compute transformed patterns P_i (length L), then count duplicates feasible with B.
    // pick max count; and lexicographically smallest pattern among achieving max.
    // Global max over permutations.

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);

    int bestCnt = -1;
    vector<int> bestS(L, 0);

    sort(idx.begin(), idx.end());
    do {
        array<int,8> C{};
        for (int x = 0; x < K; x++) C[x] = x;

        vector<vector<int>> P(N, vector<int>(L));
        for (int p = 0; p < N; p++) {
            int i = idx[p];
            int inv[8];
            for (int x = 0; x < K; x++) inv[C[x]] = x;
            for (int j = 0; j < L; j++) {
                P[p][j] = inv[T[i][j]];
            }
            array<int,8> nC{};
            for (int x = 0; x < K; x++) nC[x] = A[i][C[x]];
            C = nC;
        }

        // count identical feasible patterns
        int localBest = 0;
        vector<int> localS(L, K); // sentinel large
        for (int a = 0; a < N; a++) {
            bool feasible = true;
            for (int j = 0; j < L; j++) {
                if (B[j] != -1 && B[j] != P[a][j]) { feasible = false; break; }
            }
            if (!feasible) continue;
            int cnt = 0;
            for (int b = 0; b < N; b++) {
                if (P[b] == P[a]) cnt++;
            }
            if (cnt > localBest) {
                localBest = cnt;
                localS = P[a];
            } else if (cnt == localBest && cnt > 0) {
                if (P[a] < localS) localS = P[a];
            }
        }

        // if no feasible pattern from agents, can still choose any S but success 0
        if (localBest == 0) {
            vector<int> s(L);
            for (int j = 0; j < L; j++) s[j] = (B[j] == -1 ? 0 : B[j]);
            localS = s;
        }

        if (localBest > bestCnt) {
            bestCnt = localBest;
            bestS = localS;
        } else if (localBest == bestCnt) {
            if (localS < bestS) bestS = localS;
        }

    } while (next_permutation(idx.begin(), idx.end()));

    cout << bestCnt << "\n";
    for (int j = 0; j < L; j++) {
        if (j) cout << ' ';
        cout << (bestS[j] + 1);
    }
    cout << "\n";
    return 0;
}

This editorial was generated by gpt-5.3-codex.