結果
問題 | No.850 企業コンテスト2位 |
ユーザー | 37zigen |
提出日時 | 2019-07-05 22:16:10 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 1,456 bytes |
コンパイル時間 | 6,024 ms |
コンパイル使用メモリ | 77,436 KB |
実行使用メモリ | 74,928 KB |
平均クエリ数 | 200.11 |
最終ジャッジ日時 | 2023-09-23 17:28:22 |
合計ジャッジ時間 | 11,977 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 222 ms
74,928 KB |
testcase_01 | AC | 229 ms
72,740 KB |
testcase_02 | AC | 186 ms
72,288 KB |
testcase_03 | AC | 186 ms
72,904 KB |
testcase_04 | AC | 220 ms
72,880 KB |
testcase_05 | AC | 189 ms
70,540 KB |
testcase_06 | AC | 231 ms
73,164 KB |
testcase_07 | AC | 256 ms
73,000 KB |
testcase_08 | AC | 265 ms
72,924 KB |
testcase_09 | AC | 267 ms
73,184 KB |
testcase_10 | AC | 312 ms
73,332 KB |
testcase_11 | AC | 304 ms
73,712 KB |
testcase_12 | AC | 304 ms
73,824 KB |
testcase_13 | AC | 302 ms
73,588 KB |
testcase_14 | AC | 303 ms
73,916 KB |
testcase_15 | AC | 299 ms
74,208 KB |
testcase_16 | AC | 294 ms
73,328 KB |
testcase_17 | AC | 305 ms
73,968 KB |
testcase_18 | AC | 297 ms
73,672 KB |
testcase_19 | AC | 299 ms
74,420 KB |
testcase_20 | AC | 305 ms
70,992 KB |
testcase_21 | AC | 306 ms
73,560 KB |
testcase_22 | AC | 304 ms
73,928 KB |
testcase_23 | AC | 302 ms
74,124 KB |
testcase_24 | AC | 302 ms
73,580 KB |
testcase_25 | AC | 304 ms
74,112 KB |
testcase_26 | AC | 303 ms
74,004 KB |
testcase_27 | AC | 218 ms
72,856 KB |
ソースコード
import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } void run() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); ArrayDeque<Integer> que = new ArrayDeque<>(); for (int i = 1; i <= N; ++i) que.addLast(i); ArrayList<Integer>[] loser = new ArrayList[N]; for (int i = 0; i < N; ++i) loser[i] = new ArrayList<>(); while (que.size() > 1) { ArrayDeque<Integer> next = new ArrayDeque<>(); while (!que.isEmpty()) { if (que.size() >= 2) { int a = que.pop(); int b = que.pop(); System.out.println("? " + a + " " + b); int ans = sc.nextInt(); next.add(ans); loser[ans-1].add((a ^ b) ^ ans); } else if (que.size() == 1) { next.add(que.pop()); } } que = next; } int first = que.pop(); for (int v : loser[first-1]) que.addLast(v); // 2*n-1-n=n-1 while (que.size() > 1) { ArrayDeque<Integer> next = new ArrayDeque<>(); while (!que.isEmpty()) { if (que.size() >= 2) { System.out.println("? " + que.pop() + " " + que.pop()); int ans = sc.nextInt(); next.add(ans); } else if (que.size() == 1) { next.add(que.pop()); } } que = next; } int second = que.pop(); System.out.println("! " + second); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }