Submission #2142754
Source Code Expand
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;
const LL MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);
//first algorithm
//変数
pair<int, int> dt = make_pair(-1, -1);
vector<int> c, a;
//概略:
//複数ターンにおける動作内容のメモ。
//これにより、高負荷なcheck_best_wayの動作回数を減らせる。
//
//詳細:
//(command >> i &1)がtrueとなるindex:iに対して、
//今後石油を満たしていく
int command = -1;
bool elseCustomer = false;//客が変わった場合
//サブ関数
//入力
void input()
{
int tmp, l, r;
cin >> l >> r;
//客が変わったかの判断をここに埋め込む
elseCustomer = (l != dt.first);
dt = make_pair(l, r);
c.clear(); a.clear();
REP(i, 8) { cin >> tmp; c.push_back(tmp); }
REP(i, 8) { cin >> tmp; a.push_back(tmp); }
}
//整数 i に対して、立っているbit数を数える
int bit_count(int i)
{
int res = 0;
while (i > 0) {
if (i & 1)res++;
i >>= 1;
}
return res;
}
//タンク使用セットiに対して、所要ターン数を計算する
int needed_turn(int set)
{
//基本的にmoveは使うつもりはないので、
//タンクの中身は0 or max を前提とする
int turn = 0;
REP(i, 8) {
if (((set >> i) & 1) == 1 && a[i] == 0)turn++;
}
return turn;
}
//整数iに対して、立っているbitに対応するタンクを使用する
bool judge_way(int i)
{
int num = 0;
REP(j, 8) {
if ((i >> j) & 1)num += c[j];
}
return (num == dt.first);
}
//現状のタンクセットで、販売可能か判断
int check_best_set()
{
int res = -1;//結果のcommand
//タンクの売る組み合わせを全探索
FOR(i, 1, 256) {
//iの組み合わせで丁度売れるかどうか
if (judge_way(i)) {
//売れる場合に、所要時間が最短かどうか
if (res == -1 || needed_turn(i) < needed_turn(res)) {
res = i;
}
}
}
//とりあえずこのセットで準備します
return res;
}
//計算
void calc()
{
//客が変わってたら、問答無用でタンクの最適解を更新
//cout << "else customer: " << elseCustomer << endl;
//if (elseCustomer) {
command = check_best_set();
//}
//流石に安すぎる客は無視します。
if (dt.first < 15) {
cout << "pass" << endl;
}
//commandベースで、派生していきます
//真っ先に給油すべきタンクがある場合
else if (1 <= command && command <= 255) {
//cout << "command:" << command << endl;
int id = 0;
while (((command >> id) & 1) == 0)id++;
//commandから消す
command -= (1 << id);
//cout << "command after:" << command << endl;
cout << "fill " << id + 1 << endl;
}
//全部OKだった場合
else if (command == 0) {
int set = check_best_set();
if (needed_turn(set) == 0) {
cout << "sell " << bit_count(set);
REP(i, 8) {
if (((set >> i) & 1) ==1 )cout << " " << i + 1;
}
cout << endl;
}
//まず無いだろうけど、バグった場合ありうるので
else {
cout << "pass" << endl;
}
}
//今の客に売れるセットが無い場合
else if (command == -1) {
//空いているタンクを探す
int id = 0;
while (id < 8) {
if (c[id] == 0)break;
else id++;
}
if (id == 8) {
//総和によって対処を変える
int sum = 0;
for (auto num : c) {
sum += num;
}
//総和が大きいときは、減らす
if (sum > 50) {
int bigNum = -1;
int bigId = -1;
REP(i, c.size()) {
if (c[i] > bigNum) {
bigNum = c[i];
bigId = i;
}
}
cout << "change " << bigId + 1 << endl;
}
else if (sum < 30) {
int minNum = 334;
int minId = -1;
REP(i, c.size()) {
if (c[i] < minNum) {
minNum = c[i];
minId = i;
}
}
cout << "change " << minId + 1 << endl;
}
else {
//被りの多いやつを消す?
//これは、代理
cout << "pass" << endl;
}
}
else cout << "fill " << id + 1 << endl;
}
//未定義
else {
cout << "pass" << endl;
}
}
//デバッグ
void debug()
{
int N;
cin>>N;
}
//メイン関数
int main()
{
REP(i, 1000) {
input();
calc();
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 石油王Xの憂鬱 |
User |
toma25 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4824 Byte |
Status |
AC |
Exec Time |
50 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 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 417500 |
0 / 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 |
50 ms |
720 KB |
subtask_01_02.txt |
AC |
49 ms |
716 KB |
subtask_01_03.txt |
AC |
48 ms |
720 KB |
subtask_01_04.txt |
AC |
47 ms |
716 KB |
subtask_01_05.txt |
AC |
50 ms |
688 KB |
subtask_01_06.txt |
AC |
49 ms |
720 KB |
subtask_01_07.txt |
AC |
49 ms |
720 KB |
subtask_01_08.txt |
AC |
47 ms |
720 KB |
subtask_01_09.txt |
AC |
48 ms |
720 KB |
subtask_01_10.txt |
AC |
49 ms |
720 KB |
subtask_01_11.txt |
AC |
48 ms |
716 KB |
subtask_01_12.txt |
AC |
49 ms |
724 KB |
subtask_01_13.txt |
AC |
49 ms |
720 KB |
subtask_01_14.txt |
AC |
47 ms |
716 KB |
subtask_01_15.txt |
AC |
47 ms |
716 KB |
subtask_01_16.txt |
AC |
50 ms |
720 KB |
subtask_01_17.txt |
AC |
49 ms |
720 KB |
subtask_01_18.txt |
AC |
48 ms |
720 KB |
subtask_01_19.txt |
AC |
48 ms |
716 KB |
subtask_01_20.txt |
AC |
48 ms |
716 KB |
subtask_01_21.txt |
AC |
50 ms |
720 KB |
subtask_01_22.txt |
AC |
48 ms |
720 KB |
subtask_01_23.txt |
AC |
50 ms |
720 KB |
subtask_01_24.txt |
AC |
46 ms |
720 KB |
subtask_01_25.txt |
AC |
48 ms |
724 KB |
subtask_01_26.txt |
AC |
49 ms |
592 KB |
subtask_01_27.txt |
AC |
50 ms |
724 KB |
subtask_01_28.txt |
AC |
47 ms |
716 KB |
subtask_01_29.txt |
AC |
47 ms |
592 KB |
subtask_01_30.txt |
AC |
46 ms |
716 KB |
subtask_01_31.txt |
AC |
46 ms |
716 KB |
subtask_01_32.txt |
AC |
48 ms |
724 KB |
subtask_01_33.txt |
AC |
48 ms |
720 KB |
subtask_01_34.txt |
AC |
47 ms |
720 KB |
subtask_01_35.txt |
AC |
46 ms |
720 KB |
subtask_01_36.txt |
AC |
50 ms |
724 KB |
subtask_01_37.txt |
AC |
47 ms |
720 KB |
subtask_01_38.txt |
AC |
49 ms |
720 KB |
subtask_01_39.txt |
AC |
46 ms |
596 KB |
subtask_01_40.txt |
AC |
48 ms |
716 KB |
subtask_01_41.txt |
AC |
48 ms |
720 KB |
subtask_01_42.txt |
AC |
47 ms |
720 KB |
subtask_01_43.txt |
AC |
42 ms |
720 KB |
subtask_01_44.txt |
AC |
49 ms |
720 KB |
subtask_01_45.txt |
AC |
47 ms |
724 KB |
subtask_01_46.txt |
AC |
47 ms |
724 KB |
subtask_01_47.txt |
AC |
48 ms |
716 KB |
subtask_01_48.txt |
AC |
49 ms |
592 KB |
subtask_01_49.txt |
AC |
49 ms |
720 KB |
subtask_01_50.txt |
AC |
49 ms |
720 KB |