結果

問題 No.2018 X-Y-X
ユーザー milanis48663220
提出日時 2023-07-05 23:56:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 5,101 bytes
コンパイル時間 1,904 ms
コンパイル使用メモリ 138,324 KB
最終ジャッジ日時 2025-02-15 06:19:45
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cmath>
#include <numeric>
#include <functional>
#include <cassert>
#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
template<typename T>
vector<vector<T>> vec2d(int n, int m, T v){
    return vector<vector<T>>(n, vector<T>(m, v));
}
template<typename T>
vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));
}
template<typename T>
void print_vector(vector<T> v, char delimiter=' '){
    if(v.empty()) {
        cout << endl;
        return;
    }
    for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;
    cout << v.back() << endl;
}
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
        if (data[y] < data[x]) swap(x, y);
        data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
void test(int n){
    int m = 1<<n;
    UnionFind uf(m);
    for(int s = 0; s < m; s++){
        for(int i = 0; i+2 < n; i++){
            int a = (s&(1<<i)) ? 1 : 0;
            int b = (s&(1<<(i+2))) ? 1 : 0;
            if(a != b){
                int t = s^(1<<(i+1));
                uf.unionSet(s, t);
            }
        }
    }
    vector<vector<int>> components(m);
    for(int i = 0; i < m; i++){
        components[uf.root(i)].push_back(i);
    }
    int cnt = 0;
    for(int r = 0; r < m; r++){
        if(components[r].size() > 0){
            cnt++;
            cout << "====" << endl;
            for(int x: components[r]){
                for(int i = 0; i < n; i++){
                    if(x&(1<<i)) cout << 1;
                    else cout << 0;
                }
                cout << ' ';
            }
            cout << endl;
        }
    }
    debug_value(cnt)
}
char inv(char c){
    return 'A'+((c-'A')^1);
}
using P = pair<char, int>;
vector<P> run_length(string s){
    char c = s[0];
    int cnt = 1;
    int n = s.size();
    vector<P> ans;
    for(int i = 1; i < n; i++){
        if(c == s[i]){
            cnt++;
        }else{
            ans.push_back({c, cnt});
            c = s[i];
            cnt = 1;
        }
    }
    ans.push_back({c, cnt});
    return ans;
}
ll solve(string s, string t){
    int n = s.size();
    for(int i = 0; i < n; i++){
        int j = i/2;
        if(j%2 == 1){
            s[i] = inv(s[i]);
            t[i] = inv(t[i]);
        }
    }
    auto ps = run_length(s);
    auto pt = run_length(t);
    if(ps.size() != pt.size()){
        return -1;
    }
    ll ans = 0;
    int m = ps.size();
    int s_len = 0, t_len = 0;
    for(int i = 0; i < m; i++){
        auto [cs, xs] = ps[i];
        auto [ct, xt] = pt[i];
        if(cs != ct){
            return -1;
        }
        if(cs == 'A') {
            int l = min(s_len, t_len);
            int r = max(s_len+xs, t_len+xt);
            ans += (r-l)*2 - (xs+xt);
        }
        s_len += xs;
        t_len += xt;
    }
    return ans;
}
int naive(string s, string t){
    map<string, int> dist;
    queue<string> que;
    auto set_dist = [&](string s, int d){
        if(dist.count(s)) return;
        dist[s] = d;
        que.push(s);
    };
    set_dist(s, 0);
    int n = s.size();
    while(!que.empty()){
        string s = que.front(); que.pop();
        for(int i = 0; i+2 < n; i++){
            if(s[i] != s[i+2]) continue;
            auto t = s;
            t[i+1] = inv(s[i+1]);
            set_dist(t, dist[s]+1);
        }
    }
    if(dist.count(t)) return dist[t];
    return -1;
}
void verify(int n){
    auto f = [&](int s){
        string ans;
        for(int i = 0; i < n; i++){
            if(s&(1<<i)) ans += 'B';
            else ans += 'A';
        }
        return ans;
    };
    for(int i = 0; i < (1<<n); i++){
        string s = f(i);
        for(int j = 0; j < (1<<n); j++){
            string t = f(j);
            int s0 = solve(s, t);
            int s1 = naive(s, t);
            if(s0 != s1){
                cout << s << ' ' << t << ' ' << s0 << ' ' << s1 << endl;
            }
        }
    }
    debug_value("OK")
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n; cin >> n;
    // verify(n);
    string s, t; cin >> s >> t;
    
    cout << solve(s, t) << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0