結果
問題 | No.608 God's Maze |
ユーザー |
|
提出日時 | 2017-12-23 09:51:31 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,549 bytes |
コンパイル時間 | 2,179 ms |
コンパイル使用メモリ | 81,416 KB |
実行使用メモリ | 57,312 KB |
最終ジャッジ日時 | 2024-12-17 16:26:52 |
合計ジャッジ時間 | 13,238 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
import java.util.ArrayDeque;import java.util.Arrays;import java.util.Scanner;class Main {void run() {Scanner sc = new Scanner(System.in);int n = sc.nextInt();String S = sc.next();boolean[] a = new boolean[S.length()];for (int i = 0; i < S.length(); ++i) {a[i] = S.charAt(i) == '.';}int ans = solve(Arrays.copyOf(a, a.length), n);{int s = 0;int t = a.length - 1;while (s < t) {boolean tmp = a[s];a[s] = a[t];a[t] = tmp;++s;--t;}n = S.length() - n + 1;}ans = Math.min(ans, solve(a, n));System.out.println(ans);}ArrayDeque<Integer> dq = new ArrayDeque<>();int solve(boolean[] a, int n) {int ret = Integer.MAX_VALUE / 3;int t = a.length - 1;int s = 0;while (a[t])--t;while (a[s])++s;if (t < n - 1)return ret;int cur = 0;for (int i = 0; i < a.length; ++i) {//s->tif (s < i && i <= t) {a[i] = !a[i];++cur;}if ((s <= i && i < n - 1) || (n - 1 < i && i <= s)) {a[i] = !a[i];++cur;}}for (int i = 0; i < a.length; ++i) {if (!a[i])dq.addLast(i);}while (!dq.isEmpty()) {if (dq.size() >= 2) {int u = dq.pollFirst();int v = dq.pollFirst();cur += (v - u) * 2;} else {int u = dq.pollFirst();cur += Math.abs((t - 1) - u) * 2 + 1;}}ret = Math.min(ret, cur);return ret;}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}public static void main(String[] args) {new Main().run();}}