結果
問題 | No.1257 変わった平均値 |
ユーザー |
|
提出日時 | 2020-10-16 23:11:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,710 bytes |
コンパイル時間 | 1,644 ms |
コンパイル使用メモリ | 124,944 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-20 23:40:28 |
合計ジャッジ時間 | 2,386 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>#include<queue>#include<map>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;// struct fast_io {// fast_io(){// std::cin.tie(nullptr);// std::ios::sync_with_stdio(false);// };// } fio;#define a first.first#define b first.second#define c second.first#define z second.secondint A, B, C, D, E, F;vector<pair<int, char>> ans;void dijkstra(){// priority_queue<pair<int,pair<int,int>,pair<int,int>>>,vector<pair<int,pair<int,int>,pair<int,int>>>>,greater<pair<int,pair<int,int>,pair<int,int>>>>> q;// priority_queue<pair<int,pair<int,int>,pair<int,int>>>,vector<pair<int,pair<int,int>,pair<int,int>>>>,greater<pair<int,pair<int,int>,pair<int,int>>>>>> q;// priority_queue<pair<int,pair<pair<int,int>,pair<int,int>>>>,vector<pair<int,pair<pair<int,int>,pair<int,int>>>>,greater<pair<int,pair<pair<int,int>,pair<int,int>>>>> q;// priority_queue<pair<int,pair<int, pair<pair<int,int>,pair<int,int>>>>,vector<pair<int,pair<int, pair<pair<int,int>,pair<int,int>>>>>,greater<pair<int,pair<int, pair<pair<int,int>,pair<int,int>>>>>> q;priority_queue<pair<int, pair<pair<int,int>,pair<int,int>>>,vector<pair<int, pair<pair<int,int>,pair<int,int>>>>,greater<pair<int, pair<pair<int,int>,pair<int,int>>>>> q;map<pair<pair<int,int>,pair<int,int>>,int> d;map<pair<pair<int,int>,pair<int,int>>,pair<pair<int,int>,pair<pair<int,int>,pair<int,int>>>> d2;d[{{A,B},{C,0}}] = 1;d2[{{A,B},{C,0}}] = {{-1,-1},{{-1,-1},{-1,-1}}};q.push({1, {{A,B},{C,0}}});// cout<<"test"<<endl;while(!q.empty()){pair<int, pair<pair<int,int>,pair<int,int>>> p = q.top();q.pop();pair<pair<int,int>,pair<int,int>> v = p.second;// cout<<"A "<<v.a<<" B "<<v.b<<" C "<<v.c<<" z "<<v.z<<endl;if(min({v.a,v.b,v.c}) > max({D,E,F})) break;if(v.a == E && v.b == F && v.c ||v.a == E && v.c == F && v.b ||v.b == E && v.a == F && v.c ||v.b == E && v.c == F && v.a ||v.c == E && v.a == F && v.b ||v.c == E && v.b == F && v.a) {// cout<<"[]"<<endl;pair<pair<int,int>,pair<int,int>> V = p.second;if(V.a == D && V.b == E && V.c == F) {if(ans.size() && (int)ans.size() + 1 < d[V] - 1) return ;if(d[V] == 1) {ans.clear();ans.push_back({2,'X'});//return ;} else {// for(;V.a != -1;){// ans.push_back({1, 'A' + d2[V].first.first});// V = d2[V].second;// }ans.clear();for(;;){// cout<<"V A "<<V.a<<" B "<<V.b<<" C "<<V.c<<" "<< d2[V].first.first<<endl;if(d2[V].first.first == -1) break;ans.push_back({1, 'A' + d2[V].first.second});V = d2[V].second;// string str;// cin>>str;}return ;}} else {ans.clear();for(;;){// cout<<"V A "<<V.a<<" B "<<V.b<<" C "<<V.c<<" "<< d2[V].first.first<<endl;if(d2[V].first.first == -1) break;ans.push_back({1, 'A' + d2[V].first.second});V = d2[V].second;// string str;// cin>>str;}ans.push_back({2,'X'});}// return ;}// cout<<"<><>"<<endl;if(d.count(v) && d[v] < p.first) continue;{pair<pair<int,int>,pair<int,int>> n;n = v;n.a *= 2;n.b *= 2;if(d.count(n) == 0 || d[n] < d[v] + 2) {d[n] = d[v] + 2;d2[n] = {{1,2}, v};q.push({d[n], n});}}{pair<pair<int,int>,pair<int,int>> n;n = v;n.a *= 2;n.c *= 2;if(d.count(n) == 0 || d[n] < d[v] + 2) {d[n] = d[v] + 2;d2[n] = {{1,1}, v};q.push({d[n], n});}}{pair<pair<int,int>,pair<int,int>> n;n = v;n.b *= 2;n.c *= 2;if(d.count(n) == 0 || d[n] < d[v] + 2) {d[n] = d[v] + 2;d2[n] = {{1,0}, v};q.push({d[n], n});}}}}signed main(){cout<<fixed<<setprecision(10);cin>>A>>B>>C>>D>>E>>F;dijkstra();if(ans.size() == 0) cout<<"No"<<endl;else {cout<<"Yes"<<endl;for(int i = ans.size()-1; i >= 0; i--) {if(ans[i].first == 1) {cout<<1<<" "<<ans[i].second<<endl;cout<<1<<" "<<ans[i].second<<endl;} else {cout<<2<<endl;}}}return 0;}