Submission #1174901
Source Code Expand
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
class TimeKeeper {
public static final int SECTYPE_SEC = 0;
public static final int SECTYPE_MSEC = 1;
private final int MAX_LOOP_SIZE = 100;
private long startTime;
ArrayList<Long> pushedTime = new ArrayList<Long>();
private long[] totalLoopTime = new long[MAX_LOOP_SIZE];
private long[] prevPushedTime = new long[MAX_LOOP_SIZE];
private static TimeKeeper instance = null;
private TimeKeeper() {
reset();
}
public static TimeKeeper getInstance() {
if (instance == null)
return instance = new TimeKeeper();
else
return instance;
}
public void reset() {
startTime = System.currentTimeMillis();
Arrays.fill(totalLoopTime, 0);
Arrays.fill(prevPushedTime, 0);
pushedTime.clear();
push();
}
public void push() {
pushedTime.add(System.currentTimeMillis());
}
public void loopPush(int id) {
assert prevPushedTime[id] == 0;
prevPushedTime[id] = System.currentTimeMillis();
}
public void loopPop(int id) {
assert prevPushedTime[id] != 0;
long current = System.currentTimeMillis();
totalLoopTime[id] += current - prevPushedTime[id];
prevPushedTime[id] = 0;
}
public void show() {
{
System.out.println("---------- Nomal pushed time -----------------");
double totalTime = 0;
for (int i = 0; i < pushedTime.size() - 1; i++) {
double time = (pushedTime.get(i + 1) - pushedTime.get(i)) / 1000.0;
totalTime += time;
System.out.println(i + " : " + time + "s");
}
System.out.println("Total Time = " + totalTime + "s");
}
{
System.out.println("----------- Loop pushed time -----------------");
double totalTime = 0;
for (int i = 0; i < MAX_LOOP_SIZE; i++) {
if (totalLoopTime[i] != 0) {
System.out.println("Loop " + i + " : " + (totalLoopTime[i]/1000.0) + "s");
totalTime += totalLoopTime[i]/1000.0;
}
}
System.out.println("Total Loop Time = " + totalTime + "s");
}
}
public long getPassedTime() {
return System.currentTimeMillis() - startTime;
}
public String getPassedTimeSecond(int type) {
switch (type) {
case SECTYPE_SEC :
return (getPassedTime() / 1000.0) + "s";
case SECTYPE_MSEC :
return getPassedTime() + "ms";
}
throw new RuntimeException();
}
}
public class Main {
InputStream is;
int __t__ = 1;
int __f__ = 0;
int __FILE_DEBUG_FLAG__ = __f__;
String __DEBUG_FILE_NAME__ = "src/B3";
FastScanner in;
PrintWriter out;
/*
class State {
int turn = 0;
int[] C, A;
State(int[] C, int[] A) {
this.C = C;
this.A = A;
}
}
int N = 8;
// chokudai (pending !!)
Queue<String> build(int D, int T, int[] C, int[] A) {
State initialState = new State(C, A);
PriorityQueue<State>[] pqs = new PriorityQueue[T+1];
for (int i = 0; i <= T; i++) {
pqs[i] = new PriorityQueue<State>(new Comparator<State>() {
public int compare(State s1, State s2) {
return 0;
}
});
}
pqs[0].add(initialState);
Queue<String> result = new LinkedList<String>();
TimeKeeper timeKeeper = TimeKeeper.getInstance();
timeKeeper.reset();
main :
while (timeKeeper.getPassedTime() < 1800) {
for (int t = 0; t <= T; t++) {
State current = pqs[t].poll();
// sell
if (current.isFinished(D)) {
current.addSellCommand(D);
result = current.toAnswer();
break main;
}
if (t == T) continue;
// fill
for (int i = 0; i < N; i++) {
State next = current.fill(i);
pqs[t+1].add(next);
}
// move
for (int from = 0; from < N; from++) {
for (int to = 0; to < N; to++) {
if (current.canMove(from, to)) {
State next = current.move(from, to);
pqs[t+1].add(next);
}
}
}
// change
}
}
if (result.isEmpty())
result.add("pass");
return result;
}
*/
String sell(int D, int[] A) {
int res = -1;
int weight = -1;
main :
for (int i = 0; i < (1 << 8); i++) {
int total = 0;
int w = 0;
for (int j = 0; j < 8; j++) {
if ((i & (1 << j)) == 0) continue;
if (A[j] == 0) continue main;
total += A[j];
w += (100 - A[j] * A[j]);
}
if (total == D && weight < w) {
res = i;
weight = w;
}
}
if (res == -1) throw new RuntimeException();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 8; i++) {
if ((res & (1 << i)) != 0)
list.add(i+1);
}
String sell = "sell " + list.size();
for (int x : list)
sell += " " + x;
return sell;
}
String fill(int D, int[] C, int[] A) {
String fill = "fill ";
int res = -1;
int weight = -1;
for (int i = 0; i < (1 << 8); i++) {
int total = 0;
int w = 0;
for (int j = 0; j < 8; j++) {
if ((i & (1 << j)) == 0) continue;
total += C[j];
w += (100 - C[j] * C[j]);
}
if (total == D && weight < w) {
res = i;
weight = w;
}
}
if (res == -1) throw new RuntimeException();
for (int i = 0; i < 8; i++) {
if ((res & (1 << i)) != 0 && A[i] == 0) {
fill += (i + 1);
break;
}
}
return fill;
}
boolean isPossible(int D, int[] C) {
for (int i = 0; i < (1 << 8); i++) {
int total = 0;
for (int j = 0; j < 8; j++) {
if ((i & (1 << j)) == 0) continue;
total += C[j];
}
if (total == D) return true;
}
return false;
}
public void solve() {
Queue<String> orders = new LinkedList<>();
int[] ideal = {10, 10, 10, 10, 4, 3, 2, 1};
main :
for (int __times = 0; __times < 1000; __times++) {
int D = in.nextInt(), T = in.nextInt();
int[] C = in.nextIntArray(8);
int[] A = in.nextIntArray(8);
if (D <= 31 || !isPossible(D, C)) {
int two = -1;
for (int i = 0; i < 8; i++) {
if (C[i] <= 3) two = i;
}
if (two != -1)
System.out.println("change " + (two+1));
else
System.out.println("pass");
} else {
if (isPossible(D, A)) {
System.out.println(sell(D, A));
} else {
System.out.println(fill(D, C, A));
}
}
System.out.flush();
/*
if (orders.isEmpty()) {
orders = build2(D, T, C, A);
}
System.out.println(orders.poll());
*/
}
}
public void run() {
if (__FILE_DEBUG_FLAG__ == __t__) {
try {
is = new FileInputStream(__DEBUG_FILE_NAME__);
} catch (FileNotFoundException e) {
// TODO 自動生成された catch ブロック
e.printStackTrace();
}
System.out.println("FILE_INPUT!");
} else {
is = System.in;
}
in = new FastScanner(is);
out = new PrintWriter(System.out);
solve();
}
public static void main(String[] args) {
new Main().run();
}
public void mapDebug(int[][] a) {
System.out.println("--------map display---------");
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.printf("%3d ", a[i][j]);
}
System.out.println();
}
System.out.println("----------------------------");
System.out.println();
}
public void debug(Object... obj) {
System.out.println(Arrays.deepToString(obj));
}
class FastScanner {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public FastScanner(InputStream stream) {
this.stream = stream;
//stream = new FileInputStream(new File("dec.in"));
}
int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
boolean isEndline(int c) {
return c == '\n' || c == '\r' || c == -1;
}
int nextInt() {
return Integer.parseInt(next());
}
int[] nextIntArray(int n) {
int[] array = new int[n];
for (int i = 0; i < n; i++)
array[i] = nextInt();
return array;
}
int[][] nextIntMap(int n, int m) {
int[][] map = new int[n][m];
for (int i = 0; i < n; i++) {
map[i] = in.nextIntArray(m);
}
return map;
}
long nextLong() {
return Long.parseLong(next());
}
long[] nextLongArray(int n) {
long[] array = new long[n];
for (int i = 0; i < n; i++)
array[i] = nextLong();
return array;
}
long[][] nextLongMap(int n, int m) {
long[][] map = new long[n][m];
for (int i = 0; i < n; i++) {
map[i] = in.nextLongArray(m);
}
return map;
}
double nextDouble() {
return Double.parseDouble(next());
}
double[] nextDoubleArray(int n) {
double[] array = new double[n];
for (int i = 0; i < n; i++)
array[i] = nextDouble();
return array;
}
double[][] nextDoubleMap(int n, int m) {
double[][] map = new double[n][m];
for (int i = 0; i < n; i++) {
map[i] = in.nextDoubleArray(m);
}
return map;
}
String next() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
String[] nextStringArray(int n) {
String[] array = new String[n];
for (int i = 0; i < n; i++)
array[i] = next();
return array;
}
String nextLine() {
int c = read();
while (isEndline(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndline(c));
return res.toString();
}
}
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
hiro116s |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
6256372 |
Code Size |
10220 Byte |
Status |
AC |
Exec Time |
214 ms |
Memory |
29212 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 |
127412 / 417500 |
133005 / 417500 |
123027 / 417500 |
125995 / 417500 |
119149 / 417500 |
126940 / 417500 |
138742 / 417500 |
127312 / 417500 |
128692 / 417500 |
130647 / 417500 |
136377 / 417500 |
122503 / 417500 |
133063 / 417500 |
124339 / 417500 |
128383 / 417500 |
129020 / 417500 |
123809 / 417500 |
128452 / 417500 |
129968 / 417500 |
125493 / 417500 |
136521 / 417500 |
124637 / 417500 |
105204 / 417500 |
124922 / 417500 |
123077 / 417500 |
126431 / 417500 |
121251 / 417500 |
111430 / 417500 |
136438 / 417500 |
138485 / 417500 |
129029 / 417500 |
112910 / 417500 |
112805 / 417500 |
124503 / 417500 |
135770 / 417500 |
132867 / 417500 |
112604 / 417500 |
120178 / 417500 |
115048 / 417500 |
121016 / 417500 |
123046 / 417500 |
120479 / 417500 |
116227 / 417500 |
123837 / 417500 |
134374 / 417500 |
118718 / 417500 |
124978 / 417500 |
116226 / 417500 |
120330 / 417500 |
130703 / 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 |
AC |
180 ms |
25448 KB |
subtask_01_02.txt |
AC |
197 ms |
25244 KB |
subtask_01_03.txt |
AC |
202 ms |
21992 KB |
subtask_01_04.txt |
AC |
211 ms |
25876 KB |
subtask_01_05.txt |
AC |
201 ms |
25824 KB |
subtask_01_06.txt |
AC |
190 ms |
25432 KB |
subtask_01_07.txt |
AC |
210 ms |
25964 KB |
subtask_01_08.txt |
AC |
179 ms |
23532 KB |
subtask_01_09.txt |
AC |
210 ms |
26092 KB |
subtask_01_10.txt |
AC |
203 ms |
25756 KB |
subtask_01_11.txt |
AC |
201 ms |
23012 KB |
subtask_01_12.txt |
AC |
186 ms |
21980 KB |
subtask_01_13.txt |
AC |
193 ms |
23016 KB |
subtask_01_14.txt |
AC |
198 ms |
26012 KB |
subtask_01_15.txt |
AC |
189 ms |
25832 KB |
subtask_01_16.txt |
AC |
183 ms |
26064 KB |
subtask_01_17.txt |
AC |
203 ms |
26368 KB |
subtask_01_18.txt |
AC |
195 ms |
22168 KB |
subtask_01_19.txt |
AC |
212 ms |
27780 KB |
subtask_01_20.txt |
AC |
210 ms |
24092 KB |
subtask_01_21.txt |
AC |
184 ms |
23872 KB |
subtask_01_22.txt |
AC |
193 ms |
25252 KB |
subtask_01_23.txt |
AC |
182 ms |
23972 KB |
subtask_01_24.txt |
AC |
191 ms |
27804 KB |
subtask_01_25.txt |
AC |
209 ms |
24868 KB |
subtask_01_26.txt |
AC |
189 ms |
25732 KB |
subtask_01_27.txt |
AC |
206 ms |
23636 KB |
subtask_01_28.txt |
AC |
190 ms |
25888 KB |
subtask_01_29.txt |
AC |
198 ms |
26040 KB |
subtask_01_30.txt |
AC |
210 ms |
25872 KB |
subtask_01_31.txt |
AC |
197 ms |
27736 KB |
subtask_01_32.txt |
AC |
192 ms |
25324 KB |
subtask_01_33.txt |
AC |
202 ms |
26144 KB |
subtask_01_34.txt |
AC |
183 ms |
23284 KB |
subtask_01_35.txt |
AC |
207 ms |
24692 KB |
subtask_01_36.txt |
AC |
190 ms |
22672 KB |
subtask_01_37.txt |
AC |
182 ms |
24416 KB |
subtask_01_38.txt |
AC |
202 ms |
26132 KB |
subtask_01_39.txt |
AC |
214 ms |
24332 KB |
subtask_01_40.txt |
AC |
186 ms |
22956 KB |
subtask_01_41.txt |
AC |
186 ms |
25452 KB |
subtask_01_42.txt |
AC |
198 ms |
23948 KB |
subtask_01_43.txt |
AC |
208 ms |
24860 KB |
subtask_01_44.txt |
AC |
186 ms |
25916 KB |
subtask_01_45.txt |
AC |
207 ms |
23692 KB |
subtask_01_46.txt |
AC |
209 ms |
25372 KB |
subtask_01_47.txt |
AC |
212 ms |
29212 KB |
subtask_01_48.txt |
AC |
185 ms |
25368 KB |
subtask_01_49.txt |
AC |
198 ms |
24120 KB |
subtask_01_50.txt |
AC |
192 ms |
24468 KB |