Submission #1275479

Source Code Expand

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto M = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto s = readln.split.map!(to!int);
    auto S = s[0] - 1;
    auto G = s[1] - 1;
    auto N = readln.split.map!(to!int).array;

    bool outside(int n) {
        return (n < 0 || n >= M);
    }

    auto edges = new int[][](M, M);
    foreach (i; 0..M) {
        if (i == G) continue;
        foreach (a; A) {
            int j = i + a;
            if (outside(j)) continue;
            j += N[j];
            if (outside(j)) continue;
            edges[i][j] = 1;

            j = i - a;
            if (outside(j)) continue;
            j += N[j];
            if (outside(j)) continue;
            edges[i][j] = 1;
        }
    }


    int INF = 1 << 20;
    auto d = new int[][](M, M);
    foreach (i; 0..M) foreach (j; 0..M) d[i][j] = edges[i][j] ? 1 : INF;
    foreach (i; 0..M) d[i][i] = 0;

    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < M; k++)
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);


    int pos = S;
    while (pos != G) {
        int minv = 1000;
        int mini = -1;
        int lr = 0;
        foreach (i, a; enumerate(A)) {
            int j = pos + a;
            if (outside(j)) continue;
            j += N[j];
            if (outside(j)) continue;
            if (d[pos][j] < minv) {
                minv = d[pos][j];
                mini = i.to!int;
                lr = 1;
            }

            j = pos - a;
            if (outside(j)) continue;
            j += N[j];
            if (outside(j)) continue;
            if (d[pos][j] < minv) {
                minv = d[pos][j];
                mini = i.to!int;
                lr = -1;
            }
        }

        int dice;
        while (true) {
            dice = readln.chomp.to!int - 1;
            if (dice == mini) {
                writeln(lr);
                stdout.flush;
                int next = pos + lr * A[dice];
                pos = next + N[next];
            }
            else {
                writeln(0);
                stdout.flush;
            }
        }
    }
}

Submission Info