結果

問題 No.1257 変わった平均値
ユーザー okok
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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.second
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0