RCO presents 日本橋ハーフマラソン 本戦

Submission #2143529

Source codeソースコード

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

	//とりあえずこのセットで準備します
	if (res != -1) {
		REP(i, 8) {
			if (a[i] == 0 && ((res >> i) & 1) == 1) {
				res -= (1 << 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();
			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 
	{
		//特定の数字に出現が偏っていると、
		//Dちょうど、という数字が出にくいので
		if (mode.first >= 3) 
		{
			int id = 0;
			while (id < 8 && c[id] != mode.second)id++;
			cout << "change " << id + 1 << 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, 8) {
					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, 8) {
					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

Task問題 A - 石油王Xの憂鬱
User nameユーザ名 toa2525
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 5425 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
test_01 0 / 417500 subtask_01_01.txt
test_02 0 / 417500 subtask_01_02.txt
test_03 0 / 417500 subtask_01_03.txt
test_04 0 / 417500 subtask_01_04.txt
test_05 0 / 417500 subtask_01_05.txt
test_06 0 / 417500 subtask_01_06.txt
test_07 0 / 417500 subtask_01_07.txt
test_08 0 / 417500 subtask_01_08.txt
test_09 0 / 417500 subtask_01_09.txt
test_10 0 / 417500 subtask_01_10.txt
test_11 0 / 417500 subtask_01_11.txt
test_12 0 / 417500 subtask_01_12.txt
test_13 0 / 417500 subtask_01_13.txt
test_14 0 / 417500 subtask_01_14.txt
test_15 0 / 417500 subtask_01_15.txt
test_16 0 / 417500 subtask_01_16.txt
test_17 0 / 417500 subtask_01_17.txt
test_18 0 / 417500 subtask_01_18.txt
test_19 0 / 417500 subtask_01_19.txt
test_20 0 / 417500 subtask_01_20.txt
test_21 0 / 417500 subtask_01_21.txt
test_22 0 / 417500 subtask_01_22.txt
test_23 0 / 417500 subtask_01_23.txt
test_24 0 / 417500 subtask_01_24.txt
test_25 0 / 417500 subtask_01_25.txt
test_26 0 / 417500 subtask_01_26.txt
test_27 0 / 417500 subtask_01_27.txt
test_28 0 / 417500 subtask_01_28.txt
test_29 0 / 417500 subtask_01_29.txt
test_30 0 / 417500 subtask_01_30.txt
test_31 0 / 417500 subtask_01_31.txt
test_32 0 / 417500 subtask_01_32.txt
test_33 0 / 417500 subtask_01_33.txt
test_34 0 / 417500 subtask_01_34.txt
test_35 0 / 417500 subtask_01_35.txt
test_36 0 / 417500 subtask_01_36.txt
test_37 0 / 417500 subtask_01_37.txt
test_38 0 / 417500 subtask_01_38.txt
test_39 0 / 417500 subtask_01_39.txt
test_40 0 / 417500 subtask_01_40.txt
test_41 0 / 417500 subtask_01_41.txt
test_42 0 / 417500 subtask_01_42.txt
test_43 0 / 417500 subtask_01_43.txt
test_44 0 / 417500 subtask_01_44.txt
test_45 0 / 417500 subtask_01_45.txt
test_46 0 / 417500 subtask_01_46.txt
test_47 0 / 417500 subtask_01_47.txt
test_48 0 / 417500 subtask_01_48.txt
test_49 0 / 417500 subtask_01_49.txt
test_50 0 / 417500 subtask_01_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt WA
subtask_01_02.txt WA
subtask_01_03.txt WA
subtask_01_04.txt WA
subtask_01_05.txt WA
subtask_01_06.txt WA
subtask_01_07.txt WA
subtask_01_08.txt WA
subtask_01_09.txt WA
subtask_01_10.txt WA
subtask_01_11.txt WA
subtask_01_12.txt WA
subtask_01_13.txt WA
subtask_01_14.txt WA
subtask_01_15.txt WA
subtask_01_16.txt WA
subtask_01_17.txt WA
subtask_01_18.txt WA
subtask_01_19.txt WA
subtask_01_20.txt WA
subtask_01_21.txt WA
subtask_01_22.txt WA
subtask_01_23.txt WA
subtask_01_24.txt WA
subtask_01_25.txt WA
subtask_01_26.txt WA
subtask_01_27.txt WA
subtask_01_28.txt WA
subtask_01_29.txt WA
subtask_01_30.txt WA
subtask_01_31.txt WA
subtask_01_32.txt WA
subtask_01_33.txt WA
subtask_01_34.txt WA
subtask_01_35.txt WA
subtask_01_36.txt WA
subtask_01_37.txt WA
subtask_01_38.txt WA
subtask_01_39.txt WA
subtask_01_40.txt WA
subtask_01_41.txt WA
subtask_01_42.txt WA
subtask_01_43.txt WA
subtask_01_44.txt WA
subtask_01_45.txt WA
subtask_01_46.txt WA
subtask_01_47.txt WA
subtask_01_48.txt WA
subtask_01_49.txt WA
subtask_01_50.txt WA