結果

問題 No.332 数列をプレゼントに
ユーザー 👑 hos.lyric
提出日時 2019-01-20 21:43:12
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,776 ms / 2,000 ms
コード長 2,503 bytes
コンパイル時間 2,084 ms
コンパイル使用メモリ 154,268 KB
実行使用メモリ 8,108 KB
最終ジャッジ日時 2024-06-13 03:23:39
合計ジャッジ時間 13,426 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens
    .popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }
int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp)
    >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }
enum LIM = 10^^4;
int N;
long X;
long[] A;
void main() {
try {
for (; ; ) {
N = readInt();
X = readLong();
A = new long[N];
foreach (i; 0 .. N) {
A[i] = readLong();
}
const lim = LIM * N + 1;
auto dp = new int[lim];
dp[] = -1;
dp[0] = -2;
foreach (i; 0 .. N) {
if (A[i] <= LIM) {
foreach_reverse (x; A[i] .. lim) {
if (dp[cast(int)(x)] == -1 && dp[cast(int)(x - A[i])] != -1) {
dp[cast(int)(x)] = i;
}
}
}
}
int[] bigIs;
foreach (i; 0 .. N) {
if (A[i] > LIM) {
bigIs ~= i;
}
}
assert(bigIs.length <= 25);
string ans = "No";
foreach (p; 0 .. 1 << bigIs.length) {
long x = X;
foreach (j, i; bigIs) {
if ((p >> j) & 1) {
x -= A[i];
}
}
if (0 <= x && x < lim && dp[cast(int)(x)] != -1) {
auto used = new bool[N];
foreach (j, i; bigIs) {
if ((p >> j) & 1) {
used[i] = true;
}
}
for (; x > 0; ) {
const i = dp[cast(int)(x)];
used[i] = true;
x -= A[i];
}
ans = used.map!(b => (b ? 'o' : 'x')).to!string;
goto found;
}
}
found:
writeln(ans);
}
} catch (EOFException e) {
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0