Submission #39214597

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;
int P, L;
enum int TIME_LIMIT = 4900;

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

State resultState;

int[] sourceNumbers;
void preprocess() {
    P = (C <= 16 ? 80 : 162);
    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();
}

Submission Info

Submission Time
Task A - Excavation
User kokatsu
Language D (LDC 1.20.1)
Score 12602547
Code Size 8926 Byte
Status AC
Exec Time 4958 ms
Memory 4396 KiB

Judge Result

Set Name test_ALL
Score / Max Score 12602547 / 50000000000
Status
AC × 50
Set Name Test Cases
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt
Case Name Status Exec Time Memory
test_0000.txt AC 4929 ms 4288 KiB
test_0001.txt AC 81 ms 4228 KiB
test_0002.txt AC 4956 ms 4180 KiB
test_0003.txt AC 47 ms 3708 KiB
test_0004.txt AC 4955 ms 4324 KiB
test_0005.txt AC 4948 ms 4280 KiB
test_0006.txt AC 44 ms 4100 KiB
test_0007.txt AC 4924 ms 4284 KiB
test_0008.txt AC 4930 ms 4136 KiB
test_0009.txt AC 4931 ms 4272 KiB
test_0010.txt AC 2640 ms 4324 KiB
test_0011.txt AC 2202 ms 4040 KiB
test_0012.txt AC 1800 ms 4276 KiB
test_0013.txt AC 4941 ms 4196 KiB
test_0014.txt AC 4932 ms 4276 KiB
test_0015.txt AC 321 ms 4164 KiB
test_0016.txt AC 50 ms 4108 KiB
test_0017.txt AC 29 ms 3792 KiB
test_0018.txt AC 36 ms 4080 KiB
test_0019.txt AC 4929 ms 4272 KiB
test_0020.txt AC 4928 ms 4320 KiB
test_0021.txt AC 443 ms 4208 KiB
test_0022.txt AC 4958 ms 4256 KiB
test_0023.txt AC 44 ms 4196 KiB
test_0024.txt AC 4934 ms 4312 KiB
test_0025.txt AC 54 ms 4104 KiB
test_0026.txt AC 1788 ms 4020 KiB
test_0027.txt AC 42 ms 3708 KiB
test_0028.txt AC 33 ms 4192 KiB
test_0029.txt AC 4930 ms 4344 KiB
test_0030.txt AC 53 ms 4148 KiB
test_0031.txt AC 52 ms 4152 KiB
test_0032.txt AC 4935 ms 4396 KiB
test_0033.txt AC 2233 ms 4072 KiB
test_0034.txt AC 4940 ms 4180 KiB
test_0035.txt AC 60 ms 3980 KiB
test_0036.txt AC 4931 ms 4212 KiB
test_0037.txt AC 2893 ms 4044 KiB
test_0038.txt AC 4924 ms 4176 KiB
test_0039.txt AC 4940 ms 4388 KiB
test_0040.txt AC 30 ms 3996 KiB
test_0041.txt AC 2316 ms 4192 KiB
test_0042.txt AC 4939 ms 4196 KiB
test_0043.txt AC 50 ms 4196 KiB
test_0044.txt AC 42 ms 4144 KiB
test_0045.txt AC 39 ms 3644 KiB
test_0046.txt AC 316 ms 4032 KiB
test_0047.txt AC 4927 ms 4144 KiB
test_0048.txt AC 4929 ms 4284 KiB
test_0049.txt AC 25 ms 3632 KiB