#1171129 (C++17) No.3587 Too Good to Swap

• 問題: No.3587 Too Good to Swap
• ユーザー: GOTKAKO
• 提出日時: 2026-07-11 11:01:41
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,573 bytes
• コンパイル時間: 4,971 ms
• コンパイル使用メモリ: 232,488 KB
• 実行使用メモリ: 9,420 KB
• 最終ジャッジ日時: 2026-07-11 11:01:50
• 合計ジャッジ時間: 4,885 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	WA * 1
other	AC * 23 WA * 26

ソースコード

#include <bits/stdc++.h>
using namespace std;

bool solve(string s,string t){
    set<string> S;
    queue<string> Q; Q.push(s),S.insert(s);
    int N = s.size();
    bool ret = false;
    while(Q.size()){
        auto now = Q.front(); Q.pop();
        bool ng = false;
        for(int i=0; i<=N-4; i++) if(now.substr(i,4) == "good"){ng = true; break;}
        if(ng) continue;
        if(now == t) ret = true;
        for(int i=0; i<N-1; i++) if(now.at(i) != now.at(i+1)){
            swap(now.at(i),now.at(i+1));
            if(!S.count(now)) S.insert(now),Q.push(now);
            swap(now.at(i),now.at(i+1));
        }
    }
    //for(auto s : S) cout << s << "\n";
    return ret;
}

random_device rnd;
mt19937 mt(rnd());

void make(string &s,int N){
    s.resize(N,'a');
    while(true){
        for(auto &c : s){
            int kind = mt()%3;
            if(kind == 0) c = 'd';
            else if(kind == 1) c = 'g';
            else c = 'o';
        }
        bool ng = false;
        for(int i=0; i<=N-4; i++) if(s.substr(i,4) == "good"){ng = true; break;}
        if(ng) continue;
        break;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    bool submit = true;
    if(T > 100000) submit = false;
    while(T--){
        string s,t;
        if(!submit){
            make(s,8),t = s;
            while(true){
                shuffle(t.begin(),t.end(),mt);
                bool good = false;
                for(int i=0; i<=t.size()-4; i++) if(t.substr(i,4) == "good"){good = true; break;}
                if(good) continue;
                break;
            }
        }
        if(submit) cin >> s >> t;

        string memos = s,memot = t;
        auto no = [&]() -> void {
            cout << "No\n";
            if(!submit && solve(memos,memot)){
                cout << "Wrong No" << endl;
                cout << 1 << endl << memos << endl << memot << endl;
                exit(0);
            }
        };
        auto yes = [&]() -> void {
            cout << "Yes\n";
            if(!submit && !solve(memos,memot)){
                cout << "Wrong Yes" << endl;
                cout << 1 << endl << memos << endl << memot << endl;
                exit(0);
            }
        };

        int N = s.size();
        vector<int> Cs(26),Ct(26);
        for(auto c : s) Cs.at(c-'a')++;
        for(auto c : t) Ct.at(c-'a')++;
        if(Cs != Ct){no(); continue;}

        int gs = 0,ds = 0,os = 0,del = 0;
        bool ng = false;
        for(int i=0; i<N; i++){
            if(s.at(i) == 'g') gs++;
            else if(s.at(i) == 'd'){
                if(i < 3 || s.at(i-2) != 'o' || s.at(i-1) != 'o') break;
                for(int p=0; p<N; p++){
                    if(gs == 0) break;
                    del++;
                    if(t.at(p) == 'g') gs--;
                    else if(t.at(p) == 'd'){ng = true; break;}
                }
                if(ng) break;
                break;
            }
        }
        if(ng){no(); continue;}
        t.erase(t.begin(),t.begin()+del);
        gs = 0,ds = 0,N = t.size();
        for(auto c : t) gs += c=='g',ds += c=='d';
        if(ds == 0 || gs == 0 || ds+gs >= N-1){yes(); continue;}


        char c1 = '-',c2 = '-',c3 = '-';
        for(int i=N; i--;){
            char c = t.at(i);
            if(c1 == 'o' && c2 == 'o' && c3 == 'd' && ds == 0){ng = true; break;} 
            if(c == 'g') gs--;
            else if(c == 'd') ds--;
            c3 = c2,c2 = c1,c1 = c;    
        }
        if(ng) no();
        else yes();
    }
}