結果
問題 | No.643 Two Operations No.2 |
ユーザー | Grenache |
提出日時 | 2018-02-02 22:04:51 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 3,902 ms |
コンパイル使用メモリ | 77,000 KB |
実行使用メモリ | 56,100 KB |
最終ジャッジ日時 | 2023-08-30 02:11:12 |
合計ジャッジ時間 | 6,491 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 129 ms
55,772 KB |
testcase_01 | AC | 131 ms
55,812 KB |
testcase_02 | AC | 144 ms
55,844 KB |
testcase_03 | AC | 128 ms
55,992 KB |
testcase_04 | AC | 127 ms
55,584 KB |
testcase_05 | AC | 149 ms
56,024 KB |
testcase_06 | AC | 127 ms
55,552 KB |
testcase_07 | AC | 128 ms
56,100 KB |
testcase_08 | AC | 128 ms
56,068 KB |
testcase_09 | AC | 129 ms
55,828 KB |
testcase_10 | AC | 145 ms
56,044 KB |
testcase_11 | AC | 127 ms
55,640 KB |
testcase_12 | AC | 128 ms
55,884 KB |
ソースコード
import java.io.*; import java.util.*; public class Main_yukicoder643 { private static Scanner sc; private static Printer pr; private static void solve() { int x = sc.nextInt(); int y = sc.nextInt(); Map<Pair, Integer> dp = new HashMap<>(); dp.put(new Pair(x, y), 0); Queue<Pair> q = new ArrayDeque<>(); q.add(new Pair(x, y)); while (!q.isEmpty()) { Pair e = q.remove(); // pr.println(e); if (e.a == e.b) { int ans = dp.get(e); if (ans > 100) { pr.println(-1); } else { pr.println(ans); } // pr.println(dp.get(e)); // pr.println(e); return; } Pair tmp = new Pair(e.b, e.a); if (!dp.containsKey(tmp)) { q.add(tmp); dp.put(tmp, dp.get(e) + 1); } tmp = new Pair(e.a + e.b, e.a - e.b); if (!dp.containsKey(tmp)) { q.add(tmp); dp.put(tmp, dp.get(e) + 1); } } } private static class Pair implements Comparable<Pair> { long a; long b; Pair(long a, long b) { this.a = a; this.b = b; } @Override public int compareTo(Pair o) { if (a == o.a) { return Long.compare(b, o.b); } return Long.compare(a, o.a); } @Override public int hashCode() { return Long.hashCode(a); } @Override public boolean equals(Object obj) { return a == ((Pair)obj).a && b == ((Pair)obj).b; } @Override public String toString() { // [xxx, xxxx] StringBuilder stmp = new StringBuilder(32); stmp.append('['); stmp.append(a); stmp.append(','); stmp.append(' '); stmp.append(b); stmp.append(']'); return stmp.toString(); } } // --------------------------------------------------- public static void main(String[] args) { sc = new Scanner(System.in); pr = new Printer(System.out); solve(); pr.close(); sc.close(); } private static class Printer extends PrintWriter { Printer(PrintStream out) { super(out); } } }