Submission #1173242


Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}
//

const int TURN = 1000;
const int L = 8;
const int MAX_D = 50;

int D, T;
int C[L];
int A[L];

void input() {
    cin >> D >> T;
    REP(i, L) cin >> C[i];
    REP(i, L) cin >> A[i];
}

void fill(int idx) {
    cout << "fill " << idx+1 << endl;
}

void sell(vector<int> v) {
    cout << "sell " << v.size() << " ";
    REP(i, v.size()) {
        cout << v[i]+1;
        if(i+1 != v.size()) cout << " ";
        else cout << endl;
    }
}

void change(int idx) {
    cout << "change " << idx+1 << endl;
}

void pass() {
    cout << "pass" << endl;
}

bool fill_greedy() {
    REP(i, L) if(C[i] != A[i]) {
        fill(i);
        return true;
    }
    return false;
}

bool change_greedy(int TH_CHANGE) {
    REP(i, L) if(C[i] < TH_CHANGE) {
        change(i);
        return true;
    }
    return false;
}

bool sell_greedy(int TH_D, int TH_NUM) {
    if(D < TH_D) {
        return false;
    }
    int dp[MAX_D+1] = {};
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    REP(i, L) if(A[i] != 0) for(int s = MAX_D; s >= 0; s--) {
        if(dp[s] != -1) {
            int ns = s + A[i];
            if(ns <= MAX_D) {
                int nval = dp[s] | (1 << i);
                if(dp[ns] == -1 || __builtin_popcount(nval) < __builtin_popcount(dp[ns])) {
                    dp[ns] = nval;
                }
            }
        }
    }
    if(__builtin_popcount(dp[D]) <= TH_NUM) {
        vector<int> v;
        REP(i, L) if(dp[D] >> i & 1) {
            v.push_back(i);
        }
        sell(v);
        return true;
    }
    return false;
}

int main(){
    iostream_init();

    const int TH_D = 40; // the cap >= TH_D
    const int TH_NUM = 6; // the number of items <= TH_NUm
    const int TH_CHANGE = 6; // C_i >= TH_CHANGE

    for(int turn = 0; turn < TURN; turn++) {
        input();

        if(change_greedy(TH_CHANGE)) {
            continue;
        }
        if(fill_greedy()) {
            continue;
        }
        if(sell_greedy(TH_D, TH_NUM)) {
            continue;
        }
        pass();
    }

    return 0;
}

Submission Info

Submission Time
Task A - 石油王Xの憂鬱
User ichyo
Language C++14 (GCC 5.4.1)
Score 5526695
Code Size 2638 Byte
Status AC
Exec Time 43 ms
Memory 724 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 98468 / 417500 108237 / 417500 128373 / 417500 112593 / 417500 104440 / 417500 113581 / 417500 113820 / 417500 111114 / 417500 116080 / 417500 115788 / 417500 123368 / 417500 114827 / 417500 113428 / 417500 118913 / 417500 113606 / 417500 122768 / 417500 111298 / 417500 119115 / 417500 118842 / 417500 115460 / 417500 112219 / 417500 72073 / 417500 113737 / 417500 106998 / 417500 115269 / 417500 120655 / 417500 111633 / 417500 117365 / 417500 111645 / 417500 112340 / 417500 65991 / 417500 111203 / 417500 100639 / 417500 103796 / 417500 120108 / 417500 109125 / 417500 110887 / 417500 107605 / 417500 101102 / 417500 113567 / 417500 116052 / 417500 108049 / 417500 106095 / 417500 102421 / 417500 108787 / 417500 118685 / 417500 115012 / 417500 106085 / 417500 96866 / 417500 116567 / 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 40 ms 720 KB
subtask_01_02.txt AC 43 ms 724 KB
subtask_01_03.txt AC 40 ms 720 KB
subtask_01_04.txt AC 41 ms 716 KB
subtask_01_05.txt AC 42 ms 720 KB
subtask_01_06.txt AC 39 ms 720 KB
subtask_01_07.txt AC 39 ms 716 KB
subtask_01_08.txt AC 40 ms 720 KB
subtask_01_09.txt AC 40 ms 720 KB
subtask_01_10.txt AC 43 ms 720 KB
subtask_01_11.txt AC 43 ms 716 KB
subtask_01_12.txt AC 40 ms 720 KB
subtask_01_13.txt AC 40 ms 720 KB
subtask_01_14.txt AC 42 ms 720 KB
subtask_01_15.txt AC 39 ms 592 KB
subtask_01_16.txt AC 42 ms 724 KB
subtask_01_17.txt AC 41 ms 720 KB
subtask_01_18.txt AC 40 ms 724 KB
subtask_01_19.txt AC 40 ms 720 KB
subtask_01_20.txt AC 39 ms 716 KB
subtask_01_21.txt AC 41 ms 720 KB
subtask_01_22.txt AC 39 ms 592 KB
subtask_01_23.txt AC 38 ms 724 KB
subtask_01_24.txt AC 42 ms 720 KB
subtask_01_25.txt AC 42 ms 720 KB
subtask_01_26.txt AC 42 ms 724 KB
subtask_01_27.txt AC 42 ms 720 KB
subtask_01_28.txt AC 40 ms 716 KB
subtask_01_29.txt AC 41 ms 720 KB
subtask_01_30.txt AC 40 ms 716 KB
subtask_01_31.txt AC 37 ms 716 KB
subtask_01_32.txt AC 39 ms 716 KB
subtask_01_33.txt AC 39 ms 724 KB
subtask_01_34.txt AC 41 ms 720 KB
subtask_01_35.txt AC 41 ms 720 KB
subtask_01_36.txt AC 42 ms 720 KB
subtask_01_37.txt AC 40 ms 672 KB
subtask_01_38.txt AC 39 ms 720 KB
subtask_01_39.txt AC 38 ms 724 KB
subtask_01_40.txt AC 41 ms 720 KB
subtask_01_41.txt AC 40 ms 720 KB
subtask_01_42.txt AC 42 ms 720 KB
subtask_01_43.txt AC 42 ms 720 KB
subtask_01_44.txt AC 43 ms 720 KB
subtask_01_45.txt AC 41 ms 720 KB
subtask_01_46.txt AC 40 ms 592 KB
subtask_01_47.txt AC 41 ms 716 KB
subtask_01_48.txt AC 41 ms 720 KB
subtask_01_49.txt AC 40 ms 720 KB
subtask_01_50.txt AC 42 ms 724 KB