Submission #1173203
Source Code Expand
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
public class Main {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> find(int sum, boolean[] done) {
if (sum == d) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; ++i) {
if (done[i]) {
list.add(i);
}
}
return list;
} else if (sum > d) {
return null;
}
ArrayList<Integer> ret = null;
for (int i = 1; i <= n; ++i) {
if (!done[i]) {
done[i] = true;
ArrayList<Integer> a = find(sum + c[i], done);
if (a != null) {
ret = a;
}
done[i] = false;
}
}
return ret;
}
final int n = 8;
int d;
int[] c;
void run() {
for (int ite = 0; ite < 1000; ++ite) {
d = ni();
int t = ni();
c = new int[n + 1];
for (int i = 1; i <= n; ++i) {
c[i] = ni();
}
int[] a = new int[n + 1];
for (int i = 1; i <= n; ++i) {
a[i] = ni();
}
int target = 0;
for (int i = 0; i <= n; ++i) {
if (a[i] == 0) {
target = i;
break;
}
}
if (target == 0) {
// 組み合わせを考える.なかったらpass
ArrayList<Integer> list = find(0, new boolean[n + 1]);
if (list == null) {
System.out.println("pass");
} else {
System.out.print("sell ");
System.out.print(list.size());
for (int idx : list) {
System.out.print(" " + idx);
}
System.out.println();
}
} else {
System.out.println("fill " + target);
}
System.out.flush();
}
}
public static void main(String[] args) {
new Main().run();
}
int ni() {
return Integer.parseInt(sc.next());
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
class BIT<T> {
int n;
ArrayList<T> bit;
BiFunction<T, T, T> bif;
/**
* 1-indexed なBinary Indexed Treeを構築する
*
* @param n 容量
* @param bif 適用させる関数
* @param sup 初期値
*/
BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
this.n = n;
bit = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
bit.add(sup.get());
}
this.bif = bif;
}
/**
* iの位置の値をvで更新する
*
* @param i index
* @param v 新しい値
*/
void set(int i, T v) {
for (int x = i; x <= n; x += x & -x) {
bit.set(x, bif.apply(bit.get(x), v));
}
}
/**
* クエリー
*
* @param defaultValue 初期値
* @param i index
* @return [1, i]までfを適用した結果
*/
T reduce(T defaultValue, int i) {
T ret = defaultValue;
for (int x = i; x > 0; x -= x & -x) {
ret = bif.apply(ret, bit.get(x));
}
return ret;
}
}
class SegmentTree<T> {
int n;
ArrayList<T> dat;
BiFunction<T, T, T> bif;
Supplier<T> sup;
/**
* 0-indexed なSegment Treeを構築する
*
* @param n_ 要求容量
* @param bif 適用させる関数
* @param sup 初期値
*/
SegmentTree(int n_, BiFunction<T, T, T> bif, Supplier<T> sup) {
n = 1;
while (n < n_) n *= 2;
dat = new ArrayList<>(2 * n - 1);
for (int i = 0; i < 2 * n - 1; ++i) {
dat.add(sup.get());
}
this.bif = bif;
this.sup = sup;
}
/**
* kの位置の値をvで更新する
*
* @param k index
* @param v 新しい値
*/
void set(int k, T v) {
k += n - 1;
dat.set(k, v);
while (k > 0) {
k = (k - 1) / 2;
dat.set(k, bif.apply(dat.get(k * 2 + 1), dat.get(k * 2 + 2)));
}
}
/**
* クエリー
*
* @param l はじめ
* @param r おわり
* @return [l, r)での演算bifを適用した結果を返す
*/
T reduce(int l, int r) {
return _reduce(l, r, 0, 0, n);
}
T _reduce(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return sup.get();
if (a <= l && r <= b) return dat.get(k);
T vl = _reduce(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = _reduce(a, b, k * 2 + 2, (l + r) / 2, r);
return bif.apply(vl, vr);
}
}
class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
F f;
S s;
Pair() {
}
Pair(F f, S s) {
this.f = f;
this.s = s;
}
Pair(Pair<F, S> p) {
f = p.f;
s = p.s;
}
@Override
public int compareTo(Pair<F, S> p) {
if (f.compareTo(p.f) != 0) {
return f.compareTo(p.f);
}
return s.compareTo(p.s);
}
@Override
public int hashCode() {
return f.hashCode() ^ s.hashCode();
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || this.f == null || this.s == null) {
return false;
}
if (this.getClass() != o.getClass()) {
return false;
}
Pair p = (Pair) o;
return this.f.equals(p.f) && this.s.equals(p.s);
}
@Override
public String toString() {
return "{" + f.toString() + ", " + s.toString() + "}";
}
}
/**
* ユークリッドの互除法
*
* @return a と b の最大公約数
*/
long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
/**
* 拡張ユークリッドの互除法
*
* @return mx + ny = gcd(m, n)となるような(x, y)を返す
*/
Pair<Long, Long> gcd_ex(long m, long n) {
long[][] mat = _gcd_ex(m, n);
return new Pair<>(mat[0][0], mat[0][1]);
}
long[][] _gcd_ex(long m, long n) {
if (n == 0) {
return new long[][]{{1, 0}, {0, 1}};
}
long k = m / n;
long[][] K = new long[][]{{0, 1}, {1, -k}};
long[][] r = _gcd_ex(n, m % n);
long[][] dst = new long[2][2];
for (int y = 0; y < 2; ++y)
for (int x = 0; x < 2; ++x)
for (int i = 0; i < 2; ++i)
dst[y][x] += r[y][i] * K[i][x];
return dst;
}
long MOD = 1_000_000_007;
/**
* 繰り返し2乗法を用いたべき乗の実装
*
* @return a^r (mod 1,000,000,007)
*/
long pow(long a, long r) {
long sum = 1;
while (r > 0) {
if ((r & 1) == 1) {
sum *= a;
sum %= MOD;
}
a *= a;
a %= MOD;
r >>= 1;
}
return sum;
}
/**
* 組み合わせ
* O(n)
*
* @return {}_nC_r
*/
long C(int n, int r) {
long sum = 1;
for (int i = n; 0 < i; --i) {
sum *= i;
sum %= MOD;
}
long s = 1;
for (int i = r; 0 < i; --i) {
s *= i;
s %= MOD;
}
sum *= pow(s, MOD - 2);
sum %= MOD;
long t = 1;
for (int i = n - r; 0 < i; --i) {
t *= i;
t %= MOD;
}
sum *= pow(t, MOD - 2);
sum %= MOD;
return sum;
}
double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
/**
* 黄金分割探索
*
* @param left 下限
* @param right 上限
* @param f 探索する関数
* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
* @return 極値の座標x
*/
double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
double d1 = f.apply(c1);
double d2 = f.apply(c2);
while (right - left > 1e-9) {
if (comp.compare(d1, d2) > 0) {
right = c2;
c2 = c1;
d2 = d1;
c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
d1 = f.apply(c1);
} else {
left = c1;
c1 = c2;
d1 = d2;
c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
d2 = f.apply(c2);
}
}
return right;
}
/**
* [a,b]をm:nに内分する点を返す
*/
double divideInternally(double a, double b, double m, double n) {
return (n * a + m * b) / (m + n);
}
/**
* http://alexbowe.com/popcount-permutations/
* bitの立っている数が小さい順にループしたいときに使う。
* ex)
* <pre>
* for (int i = 0; i < 25; ++i) {
* int bits = (1 << i) - 1;
* long m = C(25, num);
* for (j = 0; j < m; ++j) {
* ...(25個の中からi個bitが立っている)
* if (bits != 0)
* bits = next_perm(bits);
* }
* }
* </pre>
*
* @param v 現在のbit列
* @return 次のbit列
*/
int next_perm(int v) {
int t = (v | (v - 1)) + 1;
return t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
/**
* http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
*/
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in) {
this.in = in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++];
else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
sindahougaii |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
0 |
Code Size |
11564 Byte |
Status |
WA |
Exec Time |
200 ms |
Memory |
27392 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
test_31 |
test_32 |
test_33 |
test_34 |
test_35 |
test_36 |
test_37 |
test_38 |
test_39 |
test_40 |
test_41 |
test_42 |
test_43 |
test_44 |
test_45 |
test_46 |
test_47 |
test_48 |
test_49 |
test_50 |
Score / Max Score |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
test_31 |
subtask_01_31.txt |
test_32 |
subtask_01_32.txt |
test_33 |
subtask_01_33.txt |
test_34 |
subtask_01_34.txt |
test_35 |
subtask_01_35.txt |
test_36 |
subtask_01_36.txt |
test_37 |
subtask_01_37.txt |
test_38 |
subtask_01_38.txt |
test_39 |
subtask_01_39.txt |
test_40 |
subtask_01_40.txt |
test_41 |
subtask_01_41.txt |
test_42 |
subtask_01_42.txt |
test_43 |
subtask_01_43.txt |
test_44 |
subtask_01_44.txt |
test_45 |
subtask_01_45.txt |
test_46 |
subtask_01_46.txt |
test_47 |
subtask_01_47.txt |
test_48 |
subtask_01_48.txt |
test_49 |
subtask_01_49.txt |
test_50 |
subtask_01_50.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
WA |
102 ms |
21024 KB |
subtask_01_02.txt |
WA |
110 ms |
23252 KB |
subtask_01_03.txt |
WA |
115 ms |
20352 KB |
subtask_01_04.txt |
WA |
107 ms |
21404 KB |
subtask_01_05.txt |
WA |
92 ms |
22180 KB |
subtask_01_06.txt |
WA |
92 ms |
20260 KB |
subtask_01_07.txt |
WA |
93 ms |
22440 KB |
subtask_01_08.txt |
WA |
100 ms |
21152 KB |
subtask_01_09.txt |
WA |
109 ms |
21956 KB |
subtask_01_10.txt |
WA |
100 ms |
21924 KB |
subtask_01_11.txt |
WA |
94 ms |
22052 KB |
subtask_01_12.txt |
WA |
121 ms |
22340 KB |
subtask_01_13.txt |
WA |
112 ms |
21224 KB |
subtask_01_14.txt |
WA |
107 ms |
22308 KB |
subtask_01_15.txt |
WA |
132 ms |
19880 KB |
subtask_01_16.txt |
WA |
94 ms |
21924 KB |
subtask_01_17.txt |
WA |
113 ms |
23220 KB |
subtask_01_18.txt |
WA |
105 ms |
22440 KB |
subtask_01_19.txt |
WA |
96 ms |
20260 KB |
subtask_01_20.txt |
WA |
118 ms |
26688 KB |
subtask_01_21.txt |
WA |
117 ms |
21500 KB |
subtask_01_22.txt |
WA |
112 ms |
21068 KB |
subtask_01_23.txt |
WA |
112 ms |
20516 KB |
subtask_01_24.txt |
WA |
95 ms |
19748 KB |
subtask_01_25.txt |
WA |
118 ms |
23620 KB |
subtask_01_26.txt |
WA |
123 ms |
25468 KB |
subtask_01_27.txt |
WA |
122 ms |
23324 KB |
subtask_01_28.txt |
WA |
200 ms |
27392 KB |
subtask_01_29.txt |
WA |
111 ms |
20332 KB |
subtask_01_30.txt |
WA |
92 ms |
18976 KB |
subtask_01_31.txt |
WA |
121 ms |
27052 KB |
subtask_01_32.txt |
WA |
115 ms |
21212 KB |
subtask_01_33.txt |
WA |
177 ms |
19748 KB |
subtask_01_34.txt |
WA |
107 ms |
22308 KB |
subtask_01_35.txt |
WA |
122 ms |
21920 KB |
subtask_01_36.txt |
WA |
123 ms |
24828 KB |
subtask_01_37.txt |
WA |
93 ms |
20260 KB |
subtask_01_38.txt |
WA |
130 ms |
23512 KB |
subtask_01_39.txt |
WA |
108 ms |
23020 KB |
subtask_01_40.txt |
WA |
93 ms |
19360 KB |
subtask_01_41.txt |
WA |
173 ms |
20540 KB |
subtask_01_42.txt |
WA |
94 ms |
20260 KB |
subtask_01_43.txt |
WA |
110 ms |
20048 KB |
subtask_01_44.txt |
WA |
106 ms |
22180 KB |
subtask_01_45.txt |
WA |
96 ms |
21156 KB |
subtask_01_46.txt |
WA |
93 ms |
18084 KB |
subtask_01_47.txt |
WA |
94 ms |
25376 KB |
subtask_01_48.txt |
WA |
102 ms |
22440 KB |
subtask_01_49.txt |
WA |
95 ms |
20132 KB |
subtask_01_50.txt |
WA |
137 ms |
22328 KB |