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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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