結果
問題 | No.332 数列をプレゼントに |
ユーザー |
|
提出日時 | 2017-02-23 20:59:05 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 2,062 bytes |
コンパイル時間 | 2,687 ms |
コンパイル使用メモリ | 81,476 KB |
実行使用メモリ | 46,380 KB |
最終ジャッジ日時 | 2024-12-24 10:44:16 |
合計ジャッジ時間 | 16,673 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; import java.util.concurrent.SynchronousQueue; class Main { static int N; static long X; static long[][] A; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); A = new long[N][2]; X = sc.nextLong(); long[] ref = new long[N]; for (int i = 0; i < N; ++i) { A[i][0] = sc.nextLong(); A[i][1] = i; ref[i] = A[i][0]; } Arrays.sort(A, new Comparator<long[]>() { @Override public int compare(long[] o1, long[] o2) { return Long.compare(o1[0], o2[0]); } }); int[] sum = new int[1_000_00]; Arrays.fill(sum, -1); for (int i = 0; i < N - 20; ++i) { for (int pos = sum.length - 1; pos >= 1; --pos) { if (sum[pos] != -1) continue; if (pos - A[i][0] < 0) continue; if (pos - A[i][0] == 0) { sum[pos] = (int) A[i][1]; continue; } if (sum[(int) (pos - A[i][0])] != -1) { sum[(int) pos] = (int) A[i][1]; } } } for (int s = 0; s < (1 << Math.min(N, 20)); ++s) { long sum2 = 0; boolean[] ans = new boolean[N]; for (int shift = 0; shift < Math.min(N, 20); ++shift) { if ((s & (1 << shift)) > 0) { sum2 += A[N - 1 - shift][0]; ans[(int) A[N - 1 - shift][1]] = true; } } if (X - sum2 < 0) continue; if (X - sum2 == 0) { for (int i = 0; i < N; ++i) { System.out.print(ans[i] ? "o" : "x"); } System.out.println(); return; } if (X - sum2 >= 1_000_00) continue; if (sum[(int) (X - sum2)] != -1) { int curIdx = (int) sum[(int) (X - sum2)]; int curSum = (int) (X - sum2); while (curIdx != -1) { ans[curIdx] = true; curSum -= (int) ref[curIdx]; curIdx = sum[curSum]; } for (int i = 0; i < N; ++i) { System.out.print(ans[i] ? "o" : "x"); } System.out.println(); return; } } System.out.println("No"); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }