提出 #39277095

---

ソースコード 拡げる

import std;

enum Response {
    bedrock = 0,
    broken = 1,
    finish = 2,
    invalid = -1
}

struct Coordinate {
    int x, y;

    int calculateDistance(Coordinate that) {
        return abs(this.x-that.x) + abs(this.y-that.y);
    }
}

int N, W, K, C;
Coordinate[] sources, houses;
int P, L;
enum int TIME_LIMIT = 4800;

struct State {
    ulong size;
    Coordinate[] coordinates;
}

State resultState;

int[] sourceNumbers;
void preprocess() {
    if (C <= 2) P = 20;
    else if (C <= 4) P = 40;
    else if (C <= 32) P = 80;
    else if (C <= 64) P = 162;
    else P = 334;

    L = N * N;

    sourceNumbers = new int[](K);

    auto distances = new int[](K);
    distances[] = int.max;
    foreach (i; 0 .. K) {
        foreach (j; 0 .. W) {
            int distance = houses[i].calculateDistance(sources[j]);
            if (distances[i] > distance) {
                distances[i] = distance;
                sourceNumbers[i] = j;
            }
        }
    }

    auto counts = new int[](W);
    foreach (s; sourceNumbers) {
        ++counts[s];
    }

    zip(distances, houses, sourceNumbers).sort!(
        (a, b) => counts[a[2]] == counts[b[2]] ? a[0] < b[0] : counts[a[2]] > counts[b[2]]
    );
}

const int[4] dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];
struct Field {
    State state;
    int[] arr;
    BitArray isBroken, isSource;

    this(int[] a, bool flag) {
        this.arr = a;

        this.isBroken.length = L;

        this.isSource.length = L;
        foreach (i; 0 .. W) {
            this.isSource[sources[i].x*N+sources[i].y] = true;
        }

        calculate(flag);
    }

    Coordinate breadthFirstSearch(Coordinate start) {
        auto distances = new int[][](N, N);
        foreach (j; 0 .. N) distances[j][] = int.max;

        Coordinate[] queue;
        queue ~= start;
        distances[start.x][start.y] = 1;
        while (!queue.empty) {
            auto f = queue.front;
            queue.popFront;

            if (this.isSource[f.x*N+f.y]) {
                return f;
            }

            foreach (i; 0 .. 4) {
                int nx = f.x + dx[i], ny = f.y + dy[i];
                if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
                if (distances[nx][ny] <= distances[f.x][f.y] + 1) continue;

                distances[nx][ny] = distances[f.x][f.y] + 1;
                queue ~= Coordinate(nx, ny);
            }
        }

        return Coordinate(-1, -1);
    }

    bool isMoveX(Coordinate start, Coordinate goal) {
        int countX;
        foreach (i; min(start.x, goal.x) .. max(start.x, goal.x)) {
            if (!this.isBroken[i*N+start.y]) ++countX;
        }
        foreach (i; min(start.y, goal.y) .. max(start.y, goal.y)+1) {
            if (!this.isBroken[goal.x*N+i]) ++countX;
        }

        int countY;
        foreach (i; min(start.y, goal.y) .. max(start.y, goal.y)) {
            if (!this.isBroken[start.x*N+i]) ++countY;
        }
        foreach (i; min(start.x, goal.x) .. max(start.x, goal.x)+1) {
            if (!this.isBroken[i*N+goal.y]) ++countY;
        }

        return countX <= countY;
    }

    void move(Coordinate start, Coordinate goal, bool isX) {
        int sx = start.x, sy = start.y;
        int gx = goal.x, gy = goal.y;

        if (isX) {
            if (sx <= gx) {
                foreach (i; sx .. gx) {
                    if (this.isBroken[i*N+sy]) return;

                    this.state.coordinates ~= Coordinate(i, sy);
                    this.isBroken[i*N+sy] = true;
                    this.isSource[i*N+sy] = true;
                }
            }
            else {
                for (int i = sx; i > gx; --i) {
                    if (this.isBroken[i*N+sy]) return;

                    this.state.coordinates ~= Coordinate(i, sy);
                    this.isBroken[i*N+sy] = true;
                    this.isSource[i*N+sy] = true;
                }
            }

            if (sy <= gy) {
                foreach (i; sy .. gy+1) {
                    if (this.isBroken[gx*N+i]) return;

                    this.state.coordinates ~= Coordinate(gx, i);
                    this.isBroken[gx*N+i] = true;
                    this.isSource[gx*N+i] = true;
                }
            }
            else {
                for (int i = sy; i >= gy; --i) {
                    if (this.isBroken[gx*N+i]) return;

                    this.state.coordinates ~= Coordinate(gx, i);
                    this.isBroken[gx*N+i] = true;
                    this.isSource[gx*N+i] = true;
                }
            }
        }
        else {
            if (sy <= gy) {
                foreach (i; sy .. gy) {
                    if (this.isBroken[sx*N+i]) return;

                    this.state.coordinates ~= Coordinate(sx, i);
                    this.isBroken[sx*N+i] = true;
                    this.isSource[sx*N+i] = true;
                }
            }
            else {
                for (int i = sy; i > gy; --i) {
                    if (this.isBroken[sx*N+i]) return;

                    this.state.coordinates ~= Coordinate(sx, i);
                    this.isBroken[sx*N+i] = true;
                    this.isSource[sx*N+i] = true;
                }
            }

            if (sx <= gx) {
                foreach (i; sx .. gx+1) {
                    if (this.isBroken[i*N+gy]) return;

                    this.state.coordinates ~= Coordinate(i, gy);
                    this.isBroken[i*N+gy] = true;
                    this.isSource[i*N+gy] = true;
                }
            }
            else {
                for (int i = sx; i >= gx; --i) {
                    if (this.isBroken[i*N+gy]) return;

                    this.state.coordinates ~= Coordinate(i, gy);
                    this.isBroken[i*N+gy] = true;
                    this.isSource[i*N+gy] = true;
                }
            }
        }
    }

    void calculate(bool flag) {
        foreach (i, a; this.arr) {
            Coordinate goal = sources[sourceNumbers[a]];
            if (i > 0) {
                goal = breadthFirstSearch(houses[a]);
            }

            bool isX = isMoveX(houses[a], goal);
            if (i == 0) isX = flag;

            move(houses[a], goal, isX);
        }

        state.size = state.coordinates.length;
    }
}

void solve() {
    SysTime startTime = Clock.currTime;

    resultState.size = ulong.max;

    preprocess();

    auto numbers = iota(K).array;
    if (K <= 6) {
        foreach (arr; numbers.permutations) {
            if ((Clock.currTime - startTime).total!"msecs" > dur!"msecs"(TIME_LIMIT).total!"msecs") {
                break;
            }

            auto fieldX = new Field(arr.array, true);
            if (resultState.size > fieldX.state.size) {
                resultState = fieldX.state;
            }

            auto fieldY = new Field(arr.array, false);
            if (resultState.size > fieldY.state.size) {
                resultState = fieldY.state;
            }
        }
    }
    else {
        bool[string] used;
        auto rnd = MinstdRand0(42);
        while ((Clock.currTime - startTime).total!"msecs" < dur!"msecs"(TIME_LIMIT).total!"msecs") {
            auto arr = numbers.dup.randomShuffle(rnd).array;
            auto str = arr.map!(a => a.to!string).join;
            if (str in used) continue;

            auto fieldX = new Field(arr, true);
            if (resultState.size > fieldX.state.size) {
                resultState = fieldX.state;
            }

            auto fieldY = new Field(arr, false);
            if (resultState.size > fieldY.state.size) {
                resultState = fieldY.state;
            }

            used[str] = true;
        }
    }

    foreach (coordinate; resultState.coordinates) {
        Response response = Response.bedrock;
        while (response == Response.bedrock) {
            int power = P;
            writefln("%d %d %d", coordinate.x, coordinate.y, power);
            stdout.flush;

            int input;
            readf("%d\n", input);

            if (input == 1) {
                response = Response.broken;
            }
            else if (input == 2) {
                response = Response.finish;
            }
            else if (input == -1) {
                response = Response.invalid;
            }

            power *= 2;
        }

        if (response == Response.finish || response == Response.invalid) {
            return;
        }
    }
}

void main() {
    readf("%d %d %d %d\n", N, W, K, C);

    sources.length = W;
    foreach (i; 0 .. W) readf("%d %d\n", sources[i].x, sources[i].y);

    houses.length = K;
    foreach (i; 0 .. K) readf("%d %d\n", houses[i].x, houses[i].y);

    solve();
}

提出情報

ジャッジ結果