結果
| 問題 | No.624 Santa Claus and The Last Dungeon |
| ユーザー |
 uwi
|
| 提出日時 | 2018-01-02 04:20:35 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,122 ms / 2,000 ms |
| コード長 | 4,671 bytes |
| コンパイル時間 | 3,987 ms |
| コンパイル使用メモリ | 83,304 KB |
| 実行使用メモリ | 79,272 KB |
| 平均クエリ数 | 361.61 |
| 最終ジャッジ日時 | 2024-07-16 15:17:10 |
| 合計ジャッジ時間 | 41,387 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
package adv2017;import java.io.PrintWriter;import java.util.Arrays;import java.util.Random;import java.util.Scanner;public class N624_5 {static Scanner in;static PrintWriter out;static String INPUT = "";static boolean DEBUG = false;static Random ugen = new Random(1);static int[] ANS = shuffle(100, ugen);static void solve(){int Q = ni();Random gen = new Random();int[] ord = shuffle(100, gen);tens = new int[100];Arrays.fill(tens, -1);ones = new int[100];Arrays.fill(ones, -1);{int[] alive = Arrays.copyOf(ord, 100);for(int i = 0;i < 9;i++){dfs(alive, 0, alive.length, i, 10);if(i <= 7){int[] nalive = new int[90-i*10];int p = 0;for(int j = 0;j < alive.length;j++){if(tens[alive[j]] == -1){nalive[p++] = alive[j];}}assert nalive.length == p;alive = nalive;}else{for(int j = 0;j < alive.length;j++){if(tens[alive[j]] == -1){tens[alive[j]] = 9;}}}}}for(int i = 0;i < 10;i++){int[] alive = new int[10];int p = 0;for(int j = 0;j < 100;j++){if(tens[j] == i){alive[p++] = j;}}assert p == 10;int[][] trials = new int[999][];int[] ress = new int[999];int[] lord = new int[10];for(int j = 0;j < 10;j++)lord[j] = j;int tp = 0;inner:do{for(int j = 0;j < tp;j++){if(count(lord, trials[j]) != ress[j]){continue inner;}}String[] ss = new String[100];Arrays.fill(ss, "??");for(int j = 0;j < 10;j++)ss[alive[lord[j]]] = "?" + j;int hit = q(ss, false)[1];if(hit == 10){for(int j = 0;j < 10;j++){ones[alive[lord[j]]] = j;}break;}else{ress[tp] = hit;trials[tp++] = Arrays.copyOf(lord, 10);}}while(nextPermutation(lord));}String[] ans = new String[100];for(int i = 0;i < 100;i++){ans[i] = "" + tens[i] + ones[i];}q(ans, true);}static int count(int[] a, int[] b){int ct = 0;for(int i = 0;i < a.length;i++){if(a[i] == b[i])ct++;}return ct;}public static boolean nextPermutation(int[] a) {int n = a.length;int i;for (i = n - 2; i >= 0 && a[i] >= a[i + 1]; i--);if (i == -1)return false;int j;for (j = i + 1; j < n && a[i] < a[j]; j++);int d = a[i];a[i] = a[j - 1];a[j - 1] = d;for (int p = i + 1, q = n - 1; p < q; p++, q--) {d = a[p];a[p] = a[q];a[q] = d;}return true;}static int[] q(String[] qs, boolean end){if(DEBUG){int[] ret = new int[3];for(int i = 0;i < 100;i++){String t = Integer.toString(100 + ANS[i]);int hit = 0;for(int j = 0;j < 2;j++){if(t.charAt(1+j) == qs[i].charAt(j)){hit++;}}ret[hit]++;}return ret;}else{for(int i = 0;i < qs.length;i++){if(i > 0)out.print(" ");out.print(qs[i]);}out.println();out.flush();if(!end){return new int[]{ni(), ni(), ni()};}else{return null;}}}//static int[] tens;static int[] ones;static void dfs(int[] alive, int l, int r, int z, int prev){if(prev == r-l){for(int i = l;i < r;i++){tens[alive[i]] = z;}return;}// tr(l, r, prev, r-l);int h = l+r>>1;String[] qs = new String[100];Arrays.fill(qs, "??");for(int i = 0;i < h-l;i++){qs[alive[l+i]] = z + "?";}int lc = q(qs, false)[1];if(lc > 0)dfs(alive, l, h, z, lc);if(prev-lc > 0)dfs(alive, h, r, z, prev-lc);}static void dfs1(int[] alive, int l, int r, int z, int prev){if(prev == r-l){for(int i = l;i < r;i++){ones[alive[i]] = z;}return;}int h = l+r>>1;String[] qs = new String[100];Arrays.fill(qs, "??");for(int i = 0;i < h-l;i++){qs[alive[l+i]] = "?" + z;}int lc = q(qs, false)[1];if(lc > 0)dfs1(alive, l, h, z, lc);if(prev-lc > 0)dfs1(alive, h, r, z, prev-lc);}public static int[] shuffle(int n, Random gen){ int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = i; for(int i = 0;i < n;i++){ int ind = gen.nextInt(n-i)+i; int d = a[i]; a[i] = a[ind]; a[ind] = d; } return a; }public static void main(String[] args) throws Exception{in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);out = new PrintWriter(System.out);solve();out.flush();}static int ni() { return Integer.parseInt(in.next()); }static long nl() { return Long.parseLong(in.next()); }static double nd() { return Double.parseDouble(in.next()); }static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }}