結果

問題 No.968 引き算をして門松列（その３）
コンテスト
ユーザー vectorcc
提出日時 2020-01-18 09:54:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,189 bytes
コンパイル時間 1,547 ms
コンパイル使用メモリ 103,404 KB
実行使用メモリ 823,040 KB
最終ジャッジ日時 2024-06-27 01:54:50
合計ジャッジ時間 5,494 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<array>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<stdlib.h>
#include<unistd.h>
#include<algorithm>
#include<sstream>

template<int N>
std::vector<int> addn(std::vector<int> a,const std::array<int,N> b){
	for(int i=0;i<N;++i)
		a[i]+=b[i];
	return a;
}
std::array<int,4> make_move(const int &cost,const int &b,const int &c,const int &d){
	std::array<int,4> move;
	move[0]=cost;
	move[1]=b;
	move[2]=c;
	move[3]=d;
	return move;
}


int max_index(const std::vector<int> v){
	int n=-1;
	int max_=~0xff;
	for(unsigned int i=0;i<v.size();++i)
		if(max_<v[i]){
			max_=v[i];
			n=i;
		}
	return n;
}
int min_index(const std::vector<int> v){
	int n=-1;
	int min_=0xffff;
	for(unsigned int i=0;i<v.size();++i)
		if(min_>v[i]){
			min_=v[i];
			n=i;
		}
	return n;
}

template<typename T>
std::vector<T> slice(const std::vector<T> &v,int start,int length=-1){
	if(length==-1)
		length=v.size();
	if(start+length>((int)v.size()))
		length=v.size();
	std::vector<T> res;
	for(int i=start;i<start+length;++i)
		res.push_back(v[i]);
	return res;
}

template<typename T>
std::vector<T> sorted(std::vector<T> v){
	std::vector<T> res=v;
	std::sort(res.begin(),res.end());
	return res;
}

int min(const std::vector<int> &v){
	int a=0xffff;
	for(int n:v)
		a=std::min(a,n);
	return a;
}

bool judge(const std::vector<int> &data){
	if(sorted(slice(data,0,3))[1]!=data[1]\
		&&data[0]!=data[1]&&data[1]!=data[2]&&data[0]!=data[2])
		return true;
	return false;
}

std::string data_tostr(const std::vector<int> &data){
	using namespace std;
	ostringstream osm;
	osm<<"("<<data[0]<<","<<data[1]<<","<<data[2]<<","<<data[3]<<")";
	return osm.str();
}


template<typename T,typename U>
void printmap(std::map<T,U> m){
	for(auto iter=m.begin();iter!=m.end();++iter)
		std::cout<<iter.first<<":"<<iter.second<<std::endl;
}

class Kadomatsu{
	std::vector<int> data_;
	std::array<std::array<int,4>,3> moves_;
	std::map<std::string,int> memo_;
	public:
		Kadomatsu(){}
		Kadomatsu(int a,int b,int c,const std::array<std::array<int,4>,3> &moves__,int cost=0){
			std::vector<int> data__;
			this->data_.push_back(a);
			this->data_.push_back(b);
			this->data_.push_back(c);
			this->data_.push_back(cost);
			moves_=moves__;
		}
		Kadomatsu(const Kadomatsu &dst){
			this->data_=dst.data();
			this->moves_=dst.moves();
			auto tmp=dst.memo();
			this->memo_=dst.memo();
		}
		std::vector<int> data()const{return this->data_;}
		std::array<std::array<int,4>,3> moves()const{return this->moves_;}
		std::map<std::string,int> memo()const{return this->memo_;}
		int run(){
			return this->min_(this->data_);
		}
		int min_(std::vector<int> data__){
			if(data__[0]<=0||data__[1]<=0||data__[2]<=0){
				this->memo_[data_tostr(data__)]=0xffff;
				return 0xffff;
			}
			if(judge(data__)){
				this->memo_[data_tostr(data__)]=data__[3];
				return data__[3];
			}
			std::vector<int> res;
			std::vector<int> tmp;
			for(auto move:this->moves_){
				tmp=addn<4>(data__,move);
				if(this->memo_.find(data_tostr(tmp))!=this->memo_.end())
					res.push_back(this->memo_[data_tostr(tmp)]);
				else{
					res.push_back(this->min_(tmp));
				}
			}
			this->memo_[data_tostr(data__)]=min(res);
			return min(res);
		}
		bool find_move(std::vector<int> &res){
			std::vector<int> data__;
			int min_=0xffff;
			int n;
			if(judge(this->data_)){
				res=this->data_;
				return false;
			}
			for(auto move:this->moves_){
				data__=addn<4>(this->data_,move);
				n=std::min(min_,this->min_(data__));
				if(n<min_){
					min_=n;
					res=data__;
				}
			}
			if(min_==0xffff){
				res=this->data_;
				res[3]=-1;
				return false;
			}
			return true;
		}
		Kadomatsu next(){
			std::vector<int> v;
			Kadomatsu res;
			this->find_move(v);
			res=Kadomatsu(v[0],v[1],v[2],this->moves_,v[3]);
			return res;
		}
		bool operator==(const Kadomatsu &dst){
			std::vector<int> tmp=dst.data();
			for(int i=0;i<3;++i)
				if(this->data_[i]!=tmp[i])
					return false;
			return true;
		}
};

int main(){
	using namespace std;
	char buf[1024];
	string s;
	vector<string> vs;
	array<array<int,4>,3> moves;
	vector<int> data;
	std::vector<int> res;
	//bool flag;
	int a,b,c;
	while(fgets(buf,1024,stdin)){
		s=buf;
		int n;
		vs.clear();
		data.clear();
		Kadomatsu k;
		if(s.find(" ")==string::npos){
		}
		else{
		while(true){
			n=s.find(" ");
			if(n==string::npos)
				break;
			vs.push_back(s.substr(0,n));
			s=s.substr(n+1);
		}
		vs.push_back(s);
		if(vs.size()>=6){
//for(auto s:vs)
//	cout<<" "<<s;
			/*
			moves[0]=make_move(-1,0,0,atoi(vs[3].c_str()));
			moves[1]=make_move(0,-1,0,atoi(vs[4].c_str()));
			moves[2]=make_move(0,0,-1,atoi(vs[5].c_str()));
			*/
			moves[0]=make_move(-1,-1,0,atoi(vs[3].c_str()));
			moves[1]=make_move(0,-1,-1,atoi(vs[4].c_str()));
			moves[2]=make_move(-1,0,-1,atoi(vs[5].c_str()));
			a=atoi(vs[0].c_str());
			b=atoi(vs[1].c_str());
			c=atoi(vs[2].c_str());
			//data.push_back(a);
			k=Kadomatsu(a,b,c,moves);
n=k.run();
if(n==0xffff)
	n=-1;
cout<<n<<endl;
/*
			Kadomatsu next;
			while(true){
				next=k.next();
				cout<<"res:"<<data_tostr(next.data())<<endl;
				if(k==next)
					break;
				k=next;
			}
*/
		}
		}
	}
}
0