Submission #1174954
Source Code Expand
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Queue;
public class Main {
public static int Q = 1000;
public static int N = 8;
public static int[] c = new int[N];
public static int[] a = new int[N];
public static int d;
public static int t;
public static int step = 0;
public static IO io = new IO();
public static boolean DEBUG = false;
public static int MAX_D = 50;
public static int HIGH = 35; //狙う客
public static int COVER_N = 7; //最大でもこれくらいしか一度に使いたくない
public static int CSUM_THRES = 60; //これくらいの総容量がほしい
public static int PREFILL = 4; //これくらいはあらかじめfillしておきたい
public static void input() {
d = io.nextInt();
t = io.nextInt();
for(int i=0;i<N;i++) {
c[i] = io.nextInt();
}
for(int i=0;i<N;i++) {
a[i] = io.nextInt();
}
}
public static void main(String[] args) throws Exception {
for(int i=0;i<Q;i++) {
step++;
input();
String move = move();
io.println(move);
io.flush();
}
}
public static Queue<String> queue = new ArrayDeque<>();
public static String changeMin() {
int min = Integer.MAX_VALUE;
int mini = -1;
for(int i=0;i<N;i++) {
int x = c[i] * 100 + a[i];
if (x < min) {
min = x;
mini = i;
}
}
return "change " + (mini + 1);
}
public static String fillBig() {
int max2 = 0;
int maxi2 = -1;
for(int i=0;i<N;i++) {
if (a[i] != c[i]) {
int x = c[i] * 100 - a[i];
if (x > max2) {
max2 = x;
maxi2 = i;
}
}
}
return "fill " + (maxi2 + 1);
}
public static String move() {
int csum = 0;
int asum = 0;
int fullcount = 0;
for(int i=0;i<N;i++) {
csum += c[i];
asum += a[i];
if (a[i] == c[i]) {
fullcount++;
}
}
if (queue.isEmpty()) {
boolean ok = false;
if (d >= HIGH || step >= 970) {
if (d >= HIGH) {
debug(String.format("%4d:",d * d) + "HIGH! " + "sum=" + csum + " t=" + t);
}else{
debug(String.format("%4d:",d * d) + "LAST! " + "sum=" + csum + " t=" + t);
}
ArrayList<String> sell = sell(99);
if (sell != null) {
ok = true;
queue.addAll(sell);
double ppt = (double) d * d / sell.size();
debug(String.format("%4d:", d * d) + "SELL " + sell.size() + "turn " + String.format("%.1fppt", ppt));
}
}
if (!ok) {
// boolean filledBig = true;
// for(int i=0;i<N;i++) {
// if (c[i] >= 9 && c[i] != a[i]) {
// filledBig = false;
// break;
// }
// }
// if (csum < CSUM_THRES && filledBig) {
// //debug(String.format("SMALL csum=%d", csum));
// return changeMin();
// }
// if (fullcount <= PREFILL || !filledBig) {
// //debug(String.format("PREFILL csum=%d asum=%d full=%d", csum, asum, fullcount));
// return fillBig();
// }
// double cover = score(c,HIGH,MAX_D,COVER_N);
// int maxi = -1;
// double max = cover;
// {
// for(int i=0;i<N;i++) {
// int temp = c[i];
// double sum = 0;
// for(int j=1;j<=10;j++) {
// c[i] = j;
// sum += score(c,HIGH,MAX_D,COVER_N);
// }
// c[i] = temp;
// double average = sum / 10;
// if (average > max) {
// max = average;
// maxi = i;
// }
// }
// }
// if (maxi == -1) {
// debug(String.format("CANNOT IMPROVE %.2f", cover));
// return "pass";
// }else{
// //debug(String.format("IMPROVE! %.2f->%.2f", cover, max));
// return "change " + (maxi + 1);
// }
double currentScore = score(c, a, COVER_N, MAX_D);
Result res = nextBestMove(c, a, COVER_N, MAX_D);
if (res.score <= currentScore + 1e-9) {
debug(String.format("CANNOT IMPROVE %.1f", currentScore));
return "pass";
}else{
debug(String.format("IMPROVE %.1f -> %.1f", currentScore, res.score));
return res.move;
}
}
}
if (!queue.isEmpty()) {
return queue.poll();
}
return "pass";
}
public static ArrayList<String> sell(int max) {
int best = Integer.MAX_VALUE;
int bestMask = 0;
LOOP: for(int i=1;i<1<<N;i++) {
int sum = 0;
int need = 0;
for(int j=0;j<N;j++) {
if ((i >> j & 1) == 1) {
if (c[j] > max) {
continue LOOP;
}
sum += c[j];
if (a[j] != c[j]) {
need++;
}
}
}
if (sum == d) {
if (need < best) {
best = need;
bestMask = i;
}
}
}
if (bestMask <= 0) {
return null;
}
if (best + 1 > t) {
return null;
}
ArrayList<String> res = new ArrayList<>();
for(int j=0;j<N;j++) {
if ((bestMask >> j & 1) == 1 && a[j] != c[j]) {
res.add("fill " + (j + 1));
}
}
String sell = "sell " + Integer.bitCount(bestMask);
for(int j=0;j<N;j++) {
if ((bestMask >> j & 1) == 1) {
sell += " " + (j + 1);
}
}
res.add(sell);
return res;
}
public static double score(int[] c,int[] a,int min,int max) {
//ok[i]のjビット目が1⇔次のターンに新しい客D=j,T=iが来たとき売るのが間に合う
long[] ok = new long[11];
int filledMask = 0;
for(int j=0;j<N;j++) {
if (a[j] == c[j]) {
filledMask |= 1 << j;
}
}
for(int i=0;i<1<<N;i++) {
int sum = 0;
for(int j=0;j<N;j++) {
if ((i >> j & 1) == 1) {
sum += c[j];
}
}
int time = Integer.bitCount(i & ~filledMask) + 1;
for(int j=time+1;j<=10;j++) {
ok[j] |= 1L << sum;
}
}
double score = 0;
for(int t=1;t<=10;t++) {
for(int d=min;d<=max;d++) {
if ((ok[t] >> d & 1) == 1) {
score += d * d;
}
}
}
return score / (max - min + 1) / 10;
}
public static Result nextBestMove(int[] c,int[] a,int min,int max) {
String bestMove = null;
double bestScore = Double.NEGATIVE_INFINITY;
//change
for(int i=0;i<N;i++) {
int tempc = c[i];
int tempa = a[i];
a[i] = 0;
double sum = 0;
for(int j=1;j<=10;j++) {
c[i] = j;
sum += score(c,a,min,max);
}
c[i] = tempc;
a[i] = tempa;
double score = sum / 10;
if (score > bestScore) {
bestScore = score;
bestMove = "change " + (i + 1);
}
}
//fill
for(int i=0;i<N;i++) {
int tempa = a[i];
a[i] = c[i];
double score = score(c,a,min,max);
if (score > bestScore) {
bestScore = score;
bestMove = "fill " + (i + 1);
}
a[i] = tempa;
}
return new Result(bestMove, bestScore);
}
public static int randInt(int min,int max) {
return (int) (Math.random() * (max - min + 1)) + min;
}
public static int lastStep = -1;
public static void debug(Object o) {
if (DEBUG) {
if (lastStep != step) {
System.err.println();
System.err.print(step + ".");
lastStep = step;
}
System.err.print(" " + o);
}
}
}
class Result {
String move;
double score;
public Result(String move, double score) {
super();
this.move = move;
this.score = score;
}
}
class IO extends PrintWriter {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public IO() { this(System.in);}
public IO(InputStream source) { super(System.out); this.in = source;}
public IO(InputStream source, OutputStream out) {
super(out);
this.in = source;
}
public IO(String fileName) throws IOException {
super(new FileOutputStream(fileName + ".out"), false);
this.in = new FileInputStream(new File(fileName + ".txt"));
}
public IO(String in,String out) throws IOException {
super(new FileOutputStream(out + ".out"), false);
this.in = new FileInputStream(new File(in + ".txt"));
}
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 static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; 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 char[] nextCharArray(int len) {
if (!hasNext()) {
throw new NoSuchElementException();
}
char[] s = new char[len];
int i = 0;
int b = readByte();
while(isPrintableChar(b)) {
if (i == len) {
throw new InputMismatchException();
}
s[i++] = (char) b;
b = readByte();
}
return s;
}
public String nextLine() {
if (!hasNextLine()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
int b = readByte();
while(!isNewLine(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();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
throw new NumberFormatException();
}
return (int) nl;
}
public char nextChar() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return (char) readByte();
}
public double nextDouble() { return Double.parseDouble(next());}
public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
piroz95 |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
7287438 |
Code Size |
11414 Byte |
Status |
AC |
Exec Time |
1158 ms |
Memory |
36984 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 |
139622 / 417500 |
148070 / 417500 |
149881 / 417500 |
147780 / 417500 |
150065 / 417500 |
150972 / 417500 |
149357 / 417500 |
139863 / 417500 |
151393 / 417500 |
144630 / 417500 |
152200 / 417500 |
141078 / 417500 |
153547 / 417500 |
153004 / 417500 |
140903 / 417500 |
148740 / 417500 |
144346 / 417500 |
151836 / 417500 |
143895 / 417500 |
140911 / 417500 |
153173 / 417500 |
145786 / 417500 |
136179 / 417500 |
145825 / 417500 |
148700 / 417500 |
145184 / 417500 |
146501 / 417500 |
149943 / 417500 |
146421 / 417500 |
147960 / 417500 |
148986 / 417500 |
135123 / 417500 |
141356 / 417500 |
142222 / 417500 |
141473 / 417500 |
146501 / 417500 |
144793 / 417500 |
145717 / 417500 |
143326 / 417500 |
146729 / 417500 |
152172 / 417500 |
138631 / 417500 |
149797 / 417500 |
145977 / 417500 |
145602 / 417500 |
144370 / 417500 |
152121 / 417500 |
138933 / 417500 |
135214 / 417500 |
140630 / 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 |
1093 ms |
35060 KB |
subtask_01_02.txt |
AC |
1058 ms |
32232 KB |
subtask_01_03.txt |
AC |
1080 ms |
35104 KB |
subtask_01_04.txt |
AC |
1088 ms |
31788 KB |
subtask_01_05.txt |
AC |
1067 ms |
35092 KB |
subtask_01_06.txt |
AC |
1090 ms |
36984 KB |
subtask_01_07.txt |
AC |
1140 ms |
33852 KB |
subtask_01_08.txt |
AC |
1083 ms |
33104 KB |
subtask_01_09.txt |
AC |
1091 ms |
34332 KB |
subtask_01_10.txt |
AC |
1091 ms |
36004 KB |
subtask_01_11.txt |
AC |
1031 ms |
32348 KB |
subtask_01_12.txt |
AC |
1117 ms |
34944 KB |
subtask_01_13.txt |
AC |
1104 ms |
35156 KB |
subtask_01_14.txt |
AC |
1073 ms |
32152 KB |
subtask_01_15.txt |
AC |
1158 ms |
31748 KB |
subtask_01_16.txt |
AC |
1089 ms |
35716 KB |
subtask_01_17.txt |
AC |
1096 ms |
31788 KB |
subtask_01_18.txt |
AC |
1097 ms |
33636 KB |
subtask_01_19.txt |
AC |
1108 ms |
31600 KB |
subtask_01_20.txt |
AC |
1095 ms |
33040 KB |
subtask_01_21.txt |
AC |
1059 ms |
32132 KB |
subtask_01_22.txt |
AC |
1093 ms |
32396 KB |
subtask_01_23.txt |
AC |
1082 ms |
32832 KB |
subtask_01_24.txt |
AC |
1085 ms |
33600 KB |
subtask_01_25.txt |
AC |
1097 ms |
34432 KB |
subtask_01_26.txt |
AC |
1069 ms |
35280 KB |
subtask_01_27.txt |
AC |
1103 ms |
32652 KB |
subtask_01_28.txt |
AC |
1111 ms |
32236 KB |
subtask_01_29.txt |
AC |
1064 ms |
36420 KB |
subtask_01_30.txt |
AC |
1083 ms |
32792 KB |
subtask_01_31.txt |
AC |
1072 ms |
34516 KB |
subtask_01_32.txt |
AC |
1125 ms |
33292 KB |
subtask_01_33.txt |
AC |
1129 ms |
31832 KB |
subtask_01_34.txt |
AC |
1096 ms |
35672 KB |
subtask_01_35.txt |
AC |
1137 ms |
35552 KB |
subtask_01_36.txt |
AC |
1102 ms |
34580 KB |
subtask_01_37.txt |
AC |
1114 ms |
35472 KB |
subtask_01_38.txt |
AC |
1101 ms |
36048 KB |
subtask_01_39.txt |
AC |
1080 ms |
34288 KB |
subtask_01_40.txt |
AC |
1071 ms |
32444 KB |
subtask_01_41.txt |
AC |
1090 ms |
34164 KB |
subtask_01_42.txt |
AC |
1085 ms |
33832 KB |
subtask_01_43.txt |
AC |
1098 ms |
33396 KB |
subtask_01_44.txt |
AC |
1123 ms |
35244 KB |
subtask_01_45.txt |
AC |
1112 ms |
34872 KB |
subtask_01_46.txt |
AC |
1092 ms |
35596 KB |
subtask_01_47.txt |
AC |
1084 ms |
34900 KB |
subtask_01_48.txt |
AC |
1123 ms |
35672 KB |
subtask_01_49.txt |
AC |
1126 ms |
35364 KB |
subtask_01_50.txt |
AC |
1109 ms |
33268 KB |