Submission #3443340


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, std.bitmanip;

immutable int MAX = 10^^5+10;

int pack(const int[] arr) {
    int mask = 0;
    foreach (a; arr) {
        mask *= 5;
        mask += a + 2;
    }
    return mask;
}

int[] unpack(int mask) {
    auto arr = new int[](5);
    foreach_reverse (i; 0..5) {
        arr[i] = mask % 5 - 2;
        mask /= 5;
    }
    return arr;
}

int f(int mask) {
    return mask.unpack.map!(i => i == 0 ? 1 : 0).array.pack;
}

int g(int mask) {
    return mask.unpack.map!(i => -i).array.pack;
}


void main() {
    auto S = readln.chomp;
    auto A = pack([-2, -1, 0, 1, 2]);

    foreach_reverse (c; S) {
        if (c == '!') {
            A = f(A);
        } else {
            A = g(A);
        }
    }

    auto prev_n = new int[](5^^5);
    auto prev_c = new char[](5^^5);
    auto dp = new int[](5^^5);
    fill(dp, 1 << 29);

    auto pq = new BinaryHeap!(Array!(Tuple!(int, int, int, char)), "a[1] > b[1]")();
    pq.insert(tuple(pack([-2, -1, 0, 1, 2]), 0, -1, '*'));

    while (!pq.empty) {
        int mask = pq.front[0];
        int dist = pq.front[1];
        int pn = pq.front[2];
        char pc = pq.front[3];
        pq.removeFront;
        if (dist >= dp[mask]) continue;
        dp[mask] = dist;
        prev_n[mask] = pn;
        prev_c[mask] = pc;

        int fmask = f(mask);
        int gmask = g(mask);
        if (dist + 1 < dp[fmask]) {
            pq.insert(tuple(fmask, dist + 1, mask, '!'));
        }
        if (dist + 1 < dp[gmask]) {
            pq.insert(tuple(gmask, dist + 1, mask, '-'));
        }
    }

    string ans = "";
    for (int p = A; prev_c[p] != '*'; p = prev_n[p]) {
        ans ~= prev_c[p];
    }
    ans.to!(dchar[]).reverse;

    ans.writeln;
}

Submission Info

Submission Time
Task E - ショートコーディング
User nebukuro09
Language D (LDC 0.17.0)
Score 100
Code Size 1964 Byte
Status AC
Exec Time 1 ms
Memory 2300 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 35
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 328 KB
01-04.txt AC 1 ms 328 KB
01-05.txt AC 1 ms 324 KB
01-06.txt AC 1 ms 324 KB
01-07.txt AC 1 ms 380 KB
01-08.txt AC 1 ms 380 KB
01-09.txt AC 1 ms 380 KB
01-10.txt AC 1 ms 380 KB
01-11.txt AC 1 ms 380 KB
01-12.txt AC 1 ms 256 KB
01-13.txt AC 1 ms 256 KB
01-14.txt AC 1 ms 328 KB
01-15.txt AC 1 ms 256 KB
01-16.txt AC 1 ms 2300 KB
01-17.txt AC 1 ms 2300 KB
01-18.txt AC 1 ms 256 KB
01-19.txt AC 1 ms 256 KB
01-20.txt AC 1 ms 256 KB
01-21.txt AC 1 ms 256 KB
01-22.txt AC 1 ms 256 KB
01-23.txt AC 1 ms 328 KB
01-24.txt AC 1 ms 256 KB
01-25.txt AC 1 ms 256 KB
01-26.txt AC 1 ms 380 KB
01-27.txt AC 1 ms 380 KB
01-28.txt AC 1 ms 380 KB
01-29.txt AC 1 ms 380 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB