結果
問題 | 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[]>() {@Overridepublic 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));}}