Submission #74339466

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
template<class T1, class T2> bool cmin(T1 &x, const T2 &y) { if (y < x) { x = y; return 1; } return 0; }
template<class T1, class T2> bool cmax(T1 &x, const T2 &y) { if (x < y) { x = y; return 1; } return 0; }
typedef pair<int,int> pii;
typedef vector<int> vc;
#define pb push_back
#define ll long long
#define lll __int128
//#define endl '\n'
#define lowbit(x) (x&-(x))
const int inf=1e18;
//const int mod=1e9+7;
const int mod=998244353;
const int N=2e5+10;
const int maxm=1e6+10;
const int maxn=2500;
const int dir[4][2]={1,0,0,1,-1,0,0,-1};
//const int dir[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
int powerr(int x,int y){int ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
int inv(int x){return powerr(x,mod-2);}
mt19937_64 rg(random_device{}());//rg()
int gcd(int x,int y){while(y){int temp=y;y=x%y;x=temp;}return x;}
inline void read(int& a){int s = 0, w = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')w = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}a = s * w;}
void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;}
#define all(v) v.begin(),v.end()
const double eps=1e-6;
#define ls i<<1
#define rs i<<1|1
void solve(){
    int n;cin>>n;
    //cout<<n<<endl;
    string a,b;cin>>a>>b;
    if(a[0]!=b[0]||a[n-1]!=b[n-1]){
        cout<<"-1"<<endl;
        return;
    }int ans=0;
    int c[n+1];memset(c,0,sizeof(c));
    set<int>ji;
    set<int>ou;

    //维护相等的位置
    for(int i=2;i<=n;i++){
        if(i%2){
            if(a[i]==a[i-2])ji.insert(i);
        }else{
            if(a[i]==a[i-2])ou.insert(i);
        }
    }ji.insert(inf);
    // for(auto&op:ji){
    //     cout<<op<<' ';
    // }cout<<endl;
    ou.insert(inf);
    for(int i=1;i<n;i++){
        while((*ji.begin())<i+1){
            auto it=ji.begin();
                ji.erase(it);
        }
        while((*ou.begin())<i+1){
            auto it=ou.begin();
            ou.erase(it);
        }
       // cout<<i<<' '<<(*ji.begin())<<' '<<(*ou.begin())<<endl;
        c[i]^=c[i-1];
        if(c[i])a[i]=(a[i]=='0')?'1':'0';
        if(a[i]!=b[i]){
            auto j=*(ji.begin());
            auto o=*(ou.begin());
            if(j==inf&&o==inf){
                cout<<"-1"<<endl;
                return;
            }
            if(j<o){
                ans+=j-i;
                c[i]^=1;
                c[j]^=1;
                auto it=ji.begin();
                ji.erase(it);
                if(j+1<n&&a[j-1]!=a[j+1]){
                if((j+1)%2){
                    ji.insert(j+1);
                }else{
                    ou.insert(j+1);
                }
                }else if(j+1<n&&a[j-1]==a[j+1]){
                    auto it=ou.begin();
                    ou.erase(it);
                }
            }else{
                ans+=o-i;
                c[i]^=1;
                c[o]^=1;
                auto it=ou.begin();
                ou.erase(it);
                if(o+1<n&&a[o-1]!=a[o+1]){
                if((o+1)%2){
                    ji.insert(o+1);
                }else{
                    ou.insert(o+1);
                }
                }else if(o+1<n&&a[o-1]==a[o+1]){
                    auto it=ji.begin();
                    ji.erase(it);
                }
            }
        }//cout<<i<<' '<<ans<<endl;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;cin>>t;
    while(t--){solve();}
}

Submission Info

Judge Result