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 |
|
|
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 |