Submission #1174378


Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static final int N = 8;
    static int demand, timeLeft, time;
    static int[] capacity = new int[8];
    static int[] amount = new int[8];
    static int THRESHOLD_SELL = 31;

    public static void main(String[] args) throws Exception {
        for (time = 0; time < 1000; time++) {
            if (time == 998) THRESHOLD_SELL = 1;
            demand = Integer.parseInt(sc.next());
            timeLeft = Integer.parseInt(sc.next());
            timeLeft = Math.min(timeLeft, 1000 - time);
            for (int j = 0; j < N; j++) {
                capacity[j] = Integer.parseInt(sc.next());
            }
            for (int j = 0; j < N; j++) {
                amount[j] = Integer.parseInt(sc.next());
            }
            action();
            System.out.flush();
        }
    }

    static void action() {
        ArrayList<Integer> filledIdx = new ArrayList<>();
        ArrayList<Integer> emptyIdx = new ArrayList<>();
        int capacitySum = 0;
        for (int i = 0; i < N; i++) {
            capacitySum += capacity[i];
            if (amount[i] > 0) {
                filledIdx.add(i);
            } else {
                emptyIdx.add(i);
            }
        }

        // sell
        if (demand >= THRESHOLD_SELL) {
            int minBits = getMinBits();
            if (minBits == 0) {
                int tanks = canSell(filledIdx);
                sellBits(filledIdx, tanks);
                return;
            } else if (minBits != -1) {
                fill(Integer.numberOfTrailingZeros(minBits));
                return;
            }
        }

        // fill
        int maxI = -1;
        int maxV = 0;
        for (int i : emptyIdx) {
            if (maxI == -1 || capacity[i] > maxV) {
                maxI = i;
                maxV = capacity[i];
            }
        }
        int changeThreshold = 3;
        if (capacitySum < 40) {
            changeThreshold = 5;
        } else if (capacitySum < 50) {
            changeThreshold = 4;
        }
        boolean doFill = maxI != -1 && capacity[maxI] > changeThreshold;
        if (doFill) {
            fill(maxI);
            return;
        }

        // change or pass
        int minIdx = 0;
        for (int i = 1; i < N; i++) {
            if (capacity[i] + amount[i] < capacity[minIdx] + amount[minIdx]) {
                minIdx = i;
            }
        }
        if (capacity[minIdx] + amount[minIdx] <= changeThreshold) {
            change(minIdx);
        } else if (timeLeft > 1) {
            pass();
        } else if (maxI != -1) {
            fill(maxI);
        } else {
            pass();
        }
    }

    static int canSell(ArrayList<Integer> filledIdx) {
        int n = filledIdx.size();
        int ret = -1;
        double value = 0;
        for (int i = 1; i < (1 << n); i++) {
            int sum = 0;
            double curV = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += amount[filledIdx.get(j)];
                    curV += 1.0 / amount[filledIdx.get(j)];
                }
            }
            if (sum == demand && curV > value) {
                ret = i;
                value = curV;
            }
        }
        return ret;
    }

    static int getMinBits() {
        int empty = 0;
        for (int i = 0; i < N; i++) {
            if (amount[i] == 0) empty |= (1 << i);
        }
        int ret = -1;
        double value = 0;
        for (int i = 1; i < (1 << N); i++) {
            int need = i & empty;
            if (Integer.bitCount(need) >= timeLeft) continue;
            int sum = 0;
            double curV = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += capacity[j];
                    curV += 1.0 / capacity[j];
                }
            }
            if (sum == demand) {
                if (ret == -1 || curV > value) {
                    ret = need;
                    value = curV;
                }
            }
        }
        return ret;
    }

    static void sellBits(ArrayList<Integer> filledIdx, int bits) {
        ArrayList<Integer> x = new ArrayList<>();
        for (int i = 0; i < filledIdx.size(); i++) {
            if ((bits & (1 << i)) != 0) x.add(filledIdx.get(i));
        }
        sell(x);
    }

    static void fill(int i) {
        System.out.println("fill " + (i + 1));
    }

    static void move(int from, int to) {
        System.out.println("move " + (from + 1) + " " + (to + 1));
    }

    static void change(int i) {
        System.out.println("change " + (i + 1));
    }

    static void pass() {
        System.out.println("pass");
    }

    static void sell(ArrayList<Integer> idx) {
        System.out.print("sell " + idx.size());
        for (int i : idx) {
            System.out.print(" " + (i + 1));
        }
        System.out.println();
    }
}

Submission Info

Submission Time
Task A - 石油王Xの憂鬱
User tomerun
Language Java8 (OpenJDK 1.8.0)
Score 7679475
Code Size 5205 Byte
Status AC
Exec Time 321 ms
Memory 36812 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 147886 / 417500 156984 / 417500 153202 / 417500 154747 / 417500 157974 / 417500 167191 / 417500 153937 / 417500 151297 / 417500 155589 / 417500 154459 / 417500 158934 / 417500 144945 / 417500 163753 / 417500 162410 / 417500 148357 / 417500 169682 / 417500 144298 / 417500 150791 / 417500 151747 / 417500 154762 / 417500 148549 / 417500 149833 / 417500 142507 / 417500 152553 / 417500 155179 / 417500 155440 / 417500 151928 / 417500 156956 / 417500 148900 / 417500 160515 / 417500 153626 / 417500 147712 / 417500 154844 / 417500 158564 / 417500 160027 / 417500 162501 / 417500 155088 / 417500 151724 / 417500 144763 / 417500 151660 / 417500 158483 / 417500 148355 / 417500 149082 / 417500 150374 / 417500 151779 / 417500 156775 / 417500 153616 / 417500 139288 / 417500 156723 / 417500 149186 / 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 297 ms 33352 KB
subtask_01_02.txt AC 296 ms 34524 KB
subtask_01_03.txt AC 321 ms 31608 KB
subtask_01_04.txt AC 288 ms 32876 KB
subtask_01_05.txt AC 268 ms 32384 KB
subtask_01_06.txt AC 318 ms 34228 KB
subtask_01_07.txt AC 305 ms 34128 KB
subtask_01_08.txt AC 302 ms 33536 KB
subtask_01_09.txt AC 287 ms 35664 KB
subtask_01_10.txt AC 298 ms 33904 KB
subtask_01_11.txt AC 288 ms 31696 KB
subtask_01_12.txt AC 280 ms 31716 KB
subtask_01_13.txt AC 295 ms 32428 KB
subtask_01_14.txt AC 288 ms 34680 KB
subtask_01_15.txt AC 287 ms 32460 KB
subtask_01_16.txt AC 275 ms 34780 KB
subtask_01_17.txt AC 292 ms 32368 KB
subtask_01_18.txt AC 319 ms 34332 KB
subtask_01_19.txt AC 297 ms 34648 KB
subtask_01_20.txt AC 280 ms 34996 KB
subtask_01_21.txt AC 283 ms 32612 KB
subtask_01_22.txt AC 289 ms 36812 KB
subtask_01_23.txt AC 282 ms 31904 KB
subtask_01_24.txt AC 289 ms 32592 KB
subtask_01_25.txt AC 316 ms 32824 KB
subtask_01_26.txt AC 300 ms 30528 KB
subtask_01_27.txt AC 303 ms 30884 KB
subtask_01_28.txt AC 285 ms 34296 KB
subtask_01_29.txt AC 273 ms 32464 KB
subtask_01_30.txt AC 314 ms 36780 KB
subtask_01_31.txt AC 314 ms 35672 KB
subtask_01_32.txt AC 270 ms 32628 KB
subtask_01_33.txt AC 302 ms 33756 KB
subtask_01_34.txt AC 285 ms 34436 KB
subtask_01_35.txt AC 283 ms 33396 KB
subtask_01_36.txt AC 281 ms 36140 KB
subtask_01_37.txt AC 270 ms 34920 KB
subtask_01_38.txt AC 296 ms 34868 KB
subtask_01_39.txt AC 295 ms 31320 KB
subtask_01_40.txt AC 295 ms 34040 KB
subtask_01_41.txt AC 307 ms 34740 KB
subtask_01_42.txt AC 313 ms 34504 KB
subtask_01_43.txt AC 283 ms 31700 KB
subtask_01_44.txt AC 300 ms 32172 KB
subtask_01_45.txt AC 285 ms 31656 KB
subtask_01_46.txt AC 309 ms 31092 KB
subtask_01_47.txt AC 273 ms 32120 KB
subtask_01_48.txt AC 316 ms 35924 KB
subtask_01_49.txt AC 272 ms 32816 KB
subtask_01_50.txt AC 312 ms 32148 KB