Submission #1174265


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(int argc, char* argv[]){
    iostream_init();

    const int TH_D = 28; // the cap >= TH_D
    const int TH_NUM = 8; // the number of items <= TH_NUm
    const int TH_CHANGE = 4; // C_i >= TH_CHANGE

    const int th_d = (argc > 1 ? atoi(argv[1]) : TH_D);
    const int th_num = (argc > 2 ? atoi(argv[2]) : TH_NUM);
    const int th_change = (argc > 3 ? atoi(argv[3]) : 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 6930600
Code Size 2847 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 139349 / 417500 141805 / 417500 140989 / 417500 133189 / 417500 130444 / 417500 136165 / 417500 155206 / 417500 136831 / 417500 138193 / 417500 142132 / 417500 146925 / 417500 138070 / 417500 144825 / 417500 140630 / 417500 137564 / 417500 137253 / 417500 123009 / 417500 124645 / 417500 139543 / 417500 133472 / 417500 148799 / 417500 139937 / 417500 125777 / 417500 143141 / 417500 135026 / 417500 151138 / 417500 130081 / 417500 138491 / 417500 137448 / 417500 140601 / 417500 149095 / 417500 136864 / 417500 132812 / 417500 143349 / 417500 146893 / 417500 136672 / 417500 135050 / 417500 131368 / 417500 135361 / 417500 134381 / 417500 136677 / 417500 135823 / 417500 144601 / 417500 145880 / 417500 146323 / 417500 142331 / 417500 138568 / 417500 141037 / 417500 131491 / 417500 135346 / 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 42 ms 720 KB
subtask_01_02.txt AC 39 ms 720 KB
subtask_01_03.txt AC 41 ms 720 KB
subtask_01_04.txt AC 38 ms 720 KB
subtask_01_05.txt AC 37 ms 720 KB
subtask_01_06.txt AC 41 ms 716 KB
subtask_01_07.txt AC 41 ms 720 KB
subtask_01_08.txt AC 42 ms 716 KB
subtask_01_09.txt AC 41 ms 720 KB
subtask_01_10.txt AC 39 ms 716 KB
subtask_01_11.txt AC 39 ms 720 KB
subtask_01_12.txt AC 41 ms 720 KB
subtask_01_13.txt AC 38 ms 720 KB
subtask_01_14.txt AC 42 ms 720 KB
subtask_01_15.txt AC 40 ms 720 KB
subtask_01_16.txt AC 43 ms 716 KB
subtask_01_17.txt AC 40 ms 724 KB
subtask_01_18.txt AC 41 ms 720 KB
subtask_01_19.txt AC 40 ms 724 KB
subtask_01_20.txt AC 41 ms 720 KB
subtask_01_21.txt AC 37 ms 720 KB
subtask_01_22.txt AC 43 ms 724 KB
subtask_01_23.txt AC 41 ms 724 KB
subtask_01_24.txt AC 42 ms 720 KB
subtask_01_25.txt AC 41 ms 724 KB
subtask_01_26.txt AC 43 ms 716 KB
subtask_01_27.txt AC 40 ms 720 KB
subtask_01_28.txt AC 40 ms 716 KB
subtask_01_29.txt AC 38 ms 720 KB
subtask_01_30.txt AC 40 ms 592 KB
subtask_01_31.txt AC 40 ms 720 KB
subtask_01_32.txt AC 43 ms 720 KB
subtask_01_33.txt AC 42 ms 720 KB
subtask_01_34.txt AC 41 ms 720 KB
subtask_01_35.txt AC 43 ms 720 KB
subtask_01_36.txt AC 42 ms 720 KB
subtask_01_37.txt AC 39 ms 724 KB
subtask_01_38.txt AC 41 ms 720 KB
subtask_01_39.txt AC 42 ms 720 KB
subtask_01_40.txt AC 40 ms 720 KB
subtask_01_41.txt AC 43 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 39 ms 720 KB
subtask_01_45.txt AC 39 ms 720 KB
subtask_01_46.txt AC 43 ms 720 KB
subtask_01_47.txt AC 42 ms 720 KB
subtask_01_48.txt AC 40 ms 720 KB
subtask_01_49.txt AC 42 ms 720 KB
subtask_01_50.txt AC 41 ms 720 KB