結果
問題 | No.968 引き算をして門松列(その3) |
ユーザー | vectorcc |
提出日時 | 2020-01-18 09:59:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 5,185 bytes |
コンパイル時間 | 1,380 ms |
コンパイル使用メモリ | 103,960 KB |
実行使用メモリ | 821,024 KB |
最終ジャッジ日時 | 2024-06-27 02:03:40 |
合計ジャッジ時間 | 5,579 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | MLE | - |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | MLE | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
ソースコード
#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; for(auto move:this->moves_){ if(this->memo_.find(data_tostr(addn<4>(data__,move)))!=this->memo_.end()) res.push_back(this->memo_[data_tostr(addn<4>(data__,move))]); else{ res.push_back(this->min_(addn<4>(data__,move))); } } 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; } */ } } } }