結果

問題 No.517 壊れたアクセサリー
コンテスト
ユーザー hedwig100
提出日時 2020-07-17 14:22:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,796 bytes
コンパイル時間 1,958 ms
コンパイル使用メモリ 174,084 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 10:23:01
合計ジャッジ時間 2,666 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i ++)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

bool is_matched(string &A,string &B,int s) {
    rep(i,min((int)A.size(),(int)B.size() - s)) {
        if (A[i] != B[i + s]) return false;
    }
    return true;
}

int main() {
    int N; cin >> N;
    vector<string> word1(N);
    rep(i,N) cin >> word1[i];
    int M; cin >> M;
    vector<string> word2(M);
    rep(i,M) cin >> word2[i];

    int tot_len1 = 0;
    rep(i,N) tot_len1 += word1[i].size();
    int tot_len2 = 0;
    rep(i,M) tot_len2 += word2[i].size();
    if (tot_len2 != tot_len1) {
        cout << -1 << '\n';
        return 0;
    }
    
    bool flag = false;
    string ans;
    rep(i,N)rep(j,M) {
        if (word1[i][0] != word2[j][0]) continue;
        int len1 = word1[i].size(),len2 = word2[j].size();
        string x = word1[i],y = word2[j];
        
        bool possible = true;
        vector<bool> used1(N,true),used2(M,true);
        used1[i] = false; used2[j] = false;
        while (len1 < tot_len1 || len2 < tot_len2) {
            if (len1 == len2) {
                possible = false;
                break;
            }
            else if (len1 > len2) {
                rep(k,M) {
                    if (used2[k] && word2[k][0] == x[len2]) {
                        if (is_matched(word2[k],x,len2)) {
                            len2 += word2[k].size();
                            y += word2[k];
                            used2[k] = false;
                        }
                        possible = false;
                        break;
                    }
                }
            }
            else if (len1 < len2) {
                rep(k,N) {
                    if (used1[k] && word1[k][0] == y[len1]) {
                        if (is_matched(word1[k],y,len1)) {
                            len1 += word1[k].size();
                            x += word1[k];
                            used1[k] = false;
                        }
                        possible = false;
                        break;
                    }
                }
            }
            //cout << x << ' ' << y << '\n';
            if (possible = false) break;
        }
        if (x == y && x.size() == tot_len1 ) possible = true;
        if (possible && flag) {
            flag = false;
            break;
        }
        else if (possible) {
            ans = x;
            flag = true;
        }
    }
    if (flag) cout << ans << '\n';
    else cout << -1 << '\n';
    return 0;
}
0