結果

問題 No.1257 変わった平均値
ユーザー okok
提出日時 2020-10-16 23:11:20
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,710 bytes
コンパイル時間 1,467 ms
コンパイル使用メモリ 121,812 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-28 05:09:31
合計ジャッジ時間 2,635 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0