题解 | 小红的数轴移动（二）

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

// 全局常量（与原C++一致）
const delta = 2010;
const INF = 1e9 + 10;
let a = []; // 存储操作距离（1-based）

// 读取输入并执行
let lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
});

rl.on('close', () => {
    solve();
});

function solve() {
    // 修复输入读取逻辑
    let ptr = 0;
    const [n, x] = lines[ptr++].split(' ').map(Number);
    const aInput = lines[ptr++].split(' ').map(Number); // 第二行是n个a[i]
    a = [0]; // 1-based 索引
    for (let i = 0; i < n; i++) {
        a.push(aInput[i]);
    }

    // 优化：用Map存储每行可达状态（key=位置j，value={minDist: 最小距离, op: 操作类型}）
    let prevDP = new Map();
    const initialJ = delta + x;
    prevDP.set(initialJ, { minDist: 0, op: -1 }); // 初始状态：0次操作，位置initialJ，距离0

    // 存储回溯信息：dp[i][j] = { prevJ: 前一个位置, op: 操作类型 }
    const backtrack = new Array(n + 1).fill(0).map(() => new Map());

    // DP状态转移（前i次操作 → 前i+1次操作）
    for (let i = 0; i < n; i++) {
        const currDP = new Map();
        const currentA = a[i + 1]; // 第i+1次操作的距离

        // 遍历前i次的所有可达状态
        for (const [j, { minDist }] of prevDP) {
            // 选择1：向右移动（j + currentA）
            const j1 = j + currentA;
            const dist1 = minDist + currentA;
            if (j1 < 4050) { // 限制范围，避免越界
                if (!currDP.has(j1) || dist1 < currDP.get(j1).minDist) {
                    currDP.set(j1, { minDist: dist1, op: 1 });
                    backtrack[i + 1].set(j1, { prevJ: j, op: 1 });
                }
            }

            // 选择2：不动（j）
            const dist2 = minDist;
            if (!currDP.has(j) || dist2 < currDP.get(j).minDist) {
                currDP.set(j, { minDist: dist2, op: 0 });
                backtrack[i + 1].set(j, { prevJ: j, op: 0 });
            }

            // 选择3：向左移动（j - currentA）
            const j2 = j - currentA;
            const dist3 = minDist + currentA;
            if (j2 >= 0) { // 限制范围，避免越界
                if (!currDP.has(j2) || dist3 < currDP.get(j2).minDist) {
                    currDP.set(j2, { minDist: dist3, op: -1 });
                    backtrack[i + 1].set(j2, { prevJ: j, op: -1 });
                }
            }
        }

        prevDP = currDP;
    }

    // 最终目标位置：delta（原点）
    const targetJ = delta;
    let totalDist;
    let reachable = prevDP.has(targetJ) && prevDP.get(targetJ).minDist <= 1e7;

    if (!reachable) {
        // 无法到达原点，输出所有操作和+顺序1~n
        totalDist = a.slice(1).reduce((acc, val) => acc + val, 0);
        console.log(totalDist);
        console.log(Array.from({ length: n }, (_, i) => i + 1).join(' '));
        return;
    }

    // 可到达原点，获取最小总距离
    totalDist = prevDP.get(targetJ).minDist;
    console.log(totalDist);

    // 回溯操作顺序（从n次操作→0次操作）
    const xx = []; // 不动的操作
    const yy = []; // 向右移动的操作
    const zz = []; // 向左移动的操作
    let ax = n;
    let ay = targetJ;

    while (ax > 0) {
        const { prevJ, op } = backtrack[ax].get(ay);
        if (op === 0) {
            xx.push(ax);
        } else if (op === 1) {
            yy.push(ax);
        } else {
            zz.push(ax);
        }
        ay = prevJ;
        ax--;
    }

    // 拼接操作顺序（与原C++逻辑一致）
    const order = [];
    let currentPos = delta + x; // 初始位置
    while (currentPos !== delta) {
        if (currentPos < delta) {
            const op = yy.pop();
            order.push(op);
            currentPos += a[op];
        } else {
            const op = zz.pop();
            order.push(op);
            currentPos -= a[op];
        }
    }
    while (xx.length > 0) {
        order.push(xx.pop());
    }

    // 输出操作顺序（确保是n个元素的排列）
    console.log(order.join(' '));
}