Submission #1174031
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 = 31; // 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 | 6938083 |
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 | 138848 / 417500 | 135004 / 417500 | 130908 / 417500 | 134944 / 417500 | 139162 / 417500 | 140905 / 417500 | 148972 / 417500 | 147528 / 417500 | 140295 / 417500 | 146303 / 417500 | 141531 / 417500 | 140218 / 417500 | 138119 / 417500 | 140596 / 417500 | 131449 / 417500 | 146739 / 417500 | 132333 / 417500 | 135341 / 417500 | 141851 / 417500 | 137371 / 417500 | 141989 / 417500 | 138818 / 417500 | 127486 / 417500 | 142517 / 417500 | 138351 / 417500 | 141563 / 417500 | 139866 / 417500 | 148517 / 417500 | 139740 / 417500 | 145524 / 417500 | 152355 / 417500 | 139204 / 417500 | 131142 / 417500 | 143337 / 417500 | 139770 / 417500 | 142724 / 417500 | 138495 / 417500 | 127633 / 417500 | 139576 / 417500 | 147635 / 417500 | 143917 / 417500 | 133256 / 417500 | 134424 / 417500 | 137944 / 417500 | 128737 / 417500 | 139616 / 417500 | 134940 / 417500 | 122021 / 417500 | 131048 / 417500 | 137521 / 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 | 40 ms | 720 KB |
subtask_01_02.txt | AC | 43 ms | 716 KB |
subtask_01_03.txt | AC | 41 ms | 716 KB |
subtask_01_04.txt | AC | 39 ms | 720 KB |
subtask_01_05.txt | AC | 39 ms | 724 KB |
subtask_01_06.txt | AC | 40 ms | 720 KB |
subtask_01_07.txt | AC | 42 ms | 720 KB |
subtask_01_08.txt | AC | 40 ms | 720 KB |
subtask_01_09.txt | AC | 43 ms | 720 KB |
subtask_01_10.txt | AC | 41 ms | 724 KB |
subtask_01_11.txt | AC | 43 ms | 724 KB |
subtask_01_12.txt | AC | 41 ms | 720 KB |
subtask_01_13.txt | AC | 41 ms | 720 KB |
subtask_01_14.txt | AC | 41 ms | 720 KB |
subtask_01_15.txt | AC | 40 ms | 720 KB |
subtask_01_16.txt | AC | 42 ms | 716 KB |
subtask_01_17.txt | AC | 42 ms | 720 KB |
subtask_01_18.txt | AC | 41 ms | 724 KB |
subtask_01_19.txt | AC | 40 ms | 596 KB |
subtask_01_20.txt | AC | 40 ms | 720 KB |
subtask_01_21.txt | AC | 42 ms | 716 KB |
subtask_01_22.txt | AC | 43 ms | 720 KB |
subtask_01_23.txt | AC | 39 ms | 716 KB |
subtask_01_24.txt | AC | 43 ms | 720 KB |
subtask_01_25.txt | AC | 42 ms | 716 KB |
subtask_01_26.txt | AC | 41 ms | 720 KB |
subtask_01_27.txt | AC | 40 ms | 720 KB |
subtask_01_28.txt | AC | 40 ms | 720 KB |
subtask_01_29.txt | AC | 39 ms | 720 KB |
subtask_01_30.txt | AC | 41 ms | 720 KB |
subtask_01_31.txt | AC | 40 ms | 720 KB |
subtask_01_32.txt | AC | 42 ms | 720 KB |
subtask_01_33.txt | AC | 41 ms | 636 KB |
subtask_01_34.txt | AC | 41 ms | 720 KB |
subtask_01_35.txt | AC | 40 ms | 720 KB |
subtask_01_36.txt | AC | 37 ms | 720 KB |
subtask_01_37.txt | AC | 40 ms | 720 KB |
subtask_01_38.txt | AC | 40 ms | 632 KB |
subtask_01_39.txt | AC | 40 ms | 720 KB |
subtask_01_40.txt | AC | 41 ms | 720 KB |
subtask_01_41.txt | AC | 41 ms | 596 KB |
subtask_01_42.txt | AC | 42 ms | 680 KB |
subtask_01_43.txt | AC | 39 ms | 712 KB |
subtask_01_44.txt | AC | 40 ms | 720 KB |
subtask_01_45.txt | AC | 42 ms | 720 KB |
subtask_01_46.txt | AC | 42 ms | 592 KB |
subtask_01_47.txt | AC | 41 ms | 724 KB |
subtask_01_48.txt | AC | 41 ms | 720 KB |
subtask_01_49.txt | AC | 42 ms | 720 KB |
subtask_01_50.txt | AC | 41 ms | 724 KB |