Submission #39204745

---

Source Code Expand

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;

enum int P = 100;
enum int TIME_LIMIT = 4500;

struct State {
    ulong size;
    Coordinate[] coordinates;
    Coordinate[] starts, goals;
    int[] arr;
}

State resultState;

int[] sourceNumbers;
void preprocess() {
    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;
            }
        }
    }
}

const int[4] dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];

struct Field {
    State state;
    int[] arr;
    bool[][] isBroken, isSource;

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

        this.isBroken = new bool[][](N, N);

        this.isSource = new bool[][](N, N);
        foreach (i; 0 .. W) {
            this.isSource[sources[i].x][sources[i].y] = true;
        }

        calculate();
    }

    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][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][start.y]) ++countX;
        }
        foreach (i; min(start.y, goal.y) .. max(start.y, goal.y)+1) {
            if (!this.isBroken[goal.x][i]) ++countX;
        }

        int countY;
        foreach (i; min(start.y, goal.y) .. max(start.y, goal.y)) {
            if (!this.isBroken[start.x][i]) ++countY;
        }
        foreach (i; min(start.x, goal.x) .. max(start.x, goal.x)+1) {
            if (!this.isBroken[i][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][sy]) return;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    resultState.size = ulong.max;

    preprocess();

    auto rnd = MinstdRand0(42);

    auto numbers = iota(K).array;
    while ((Clock.currTime - startTime).total!"msecs" < dur!"msecs"(TIME_LIMIT).total!"msecs") {
        auto arr = numbers.dup.randomShuffle(rnd).array;

        auto field = new Field(arr);

        if (resultState.size > field.state.size) {
            resultState = field.state;
        }
    }


    foreach (coordinate; resultState.coordinates) {
        Response response = Response.bedrock;
        while (response == Response.bedrock) {
            writefln("%d %d %d", coordinate.x, coordinate.y, P);
            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;
            }
        }

        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();
}

Submission Info

Judge Result