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