Submission #2142840


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;
}

//タンクの最頻値生成
pair<int,int> make_mode_of_tank()
{
	vector<int> freq(11, 0);
	for (int num : c) {
		freq[num]++;
	}

	int maxNum = -1;
	int maxId = -1;
	FOR(i, 1, 11) {
		if (freq[i] > maxNum) {
			maxNum = freq[i];
			maxId = i;
		}
	}
	return make_pair(maxNum, maxId);
}

//計算
void calc()
{
	//現状の客に対する、最適タンク解を更新
	if (elseCustomer)command = check_best_set();

	//タンクの頻度分布生成
	auto mode = make_mode_of_tank();



	//上客で、こちらがしっかり販売出来るときのみ、
	//しっかりと応対します(他は知らん)
	const int dress_code = 20;
	if (dt.first >= dress_code &&
		command != -1 &&
		needed_turn(command)<dt.second) 
	{
		//タンクを補充する必要がある
		if (command != 0) 
		{
			int id = 0;
			while (((command >> id) & 1) == 0)id++;
			command -= (1 << id);
			cout << "fill " << id + 1 << endl;
		}
		//もう大丈夫。売ろう(若干不安)
		else
		{
			int set = check_best_set();
			cout << "sell " << bit_count(set);
			REP(i, 8) {
				if (((set >> i) & 1) == 1)cout << " " << i + 1;
			}
			cout << endl;
		}
	}
	else 
	{
		//特定の数字に出現が偏っていると、
		//Dちょうど、という数字が出にくいので
		if (mode.first >= 3) 
		{
			int id = 0;
			while (id < 8 && c[id] != mode.second)id++;
			cout << "change " << id << endl;
		}
		//そうじゃないなら、総和が大きすぎず少なすぎずにさせる
		else
		{
			//総和によって対処を変える
			int sum = 0;
			for (auto num : c) sum += num;


			const int upper_max = 60;
			const int lower_min = 30;

			//総和が大きいときは、減らす
			if (sum > upper_max)
			{
				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 < lower_min)
			{
				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
			{
				//とりあえず端から埋めていく
				int id = 0;
				while (id < 8 && a[id] != 0)id++;

				if (id < 8) {
					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 5232 Byte
Status WA
Exec Time 13 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
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 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 WA 5 ms 720 KB
subtask_01_02.txt WA 7 ms 720 KB
subtask_01_03.txt WA 11 ms 592 KB
subtask_01_04.txt WA 4 ms 724 KB
subtask_01_05.txt WA 5 ms 720 KB
subtask_01_06.txt WA 8 ms 720 KB
subtask_01_07.txt WA 8 ms 720 KB
subtask_01_08.txt WA 5 ms 720 KB
subtask_01_09.txt WA 7 ms 720 KB
subtask_01_10.txt WA 12 ms 724 KB
subtask_01_11.txt WA 4 ms 720 KB
subtask_01_12.txt WA 6 ms 716 KB
subtask_01_13.txt WA 6 ms 596 KB
subtask_01_14.txt WA 13 ms 720 KB
subtask_01_15.txt WA 6 ms 720 KB
subtask_01_16.txt WA 7 ms 720 KB
subtask_01_17.txt WA 6 ms 720 KB
subtask_01_18.txt WA 6 ms 724 KB
subtask_01_19.txt WA 4 ms 720 KB
subtask_01_20.txt WA 4 ms 720 KB
subtask_01_21.txt WA 5 ms 716 KB
subtask_01_22.txt WA 6 ms 724 KB
subtask_01_23.txt WA 7 ms 716 KB
subtask_01_24.txt WA 4 ms 716 KB
subtask_01_25.txt WA 8 ms 720 KB
subtask_01_26.txt WA 4 ms 720 KB
subtask_01_27.txt WA 4 ms 724 KB
subtask_01_28.txt WA 6 ms 724 KB
subtask_01_29.txt WA 4 ms 720 KB
subtask_01_30.txt WA 8 ms 720 KB
subtask_01_31.txt WA 5 ms 720 KB
subtask_01_32.txt WA 6 ms 720 KB
subtask_01_33.txt WA 8 ms 720 KB
subtask_01_34.txt WA 4 ms 720 KB
subtask_01_35.txt WA 5 ms 716 KB
subtask_01_36.txt WA 4 ms 720 KB
subtask_01_37.txt WA 8 ms 716 KB
subtask_01_38.txt WA 4 ms 720 KB
subtask_01_39.txt WA 5 ms 724 KB
subtask_01_40.txt WA 6 ms 716 KB
subtask_01_41.txt WA 6 ms 596 KB
subtask_01_42.txt WA 4 ms 720 KB
subtask_01_43.txt WA 6 ms 720 KB
subtask_01_44.txt WA 5 ms 720 KB
subtask_01_45.txt WA 7 ms 720 KB
subtask_01_46.txt WA 6 ms 716 KB
subtask_01_47.txt WA 5 ms 724 KB
subtask_01_48.txt WA 4 ms 724 KB
subtask_01_49.txt WA 5 ms 720 KB
subtask_01_50.txt WA 6 ms 720 KB