結果
問題 |
No.2018 X-Y-X
|
ユーザー |
|
提出日時 | 2025-07-28 13:52:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,464 bytes |
コンパイル時間 | 3,022 ms |
コンパイル使用メモリ | 275,956 KB |
実行使用メモリ | 12,404 KB |
最終ジャッジ日時 | 2025-07-28 13:52:19 |
合計ジャッジ時間 | 4,503 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e7+5; const ll INF=1e18; bool Mst; ll ans; int n; string S,T; int s[N],t[N]; bool tag[N],gt[N]; void solve(){ cin>>n; cin>>S>>T; for(int i=0;i<n;i++)s[i]=S[i]-'A',t[i]=T[i]-'A'; if(s[0]!=t[0]||s[n-1]!=t[n-1]){ cout<<"-1\n"; return ; } for(int i=0;i<n;i++)tag[i]=0; ans=0; int lasp=-1; for(int i=1;i<n-1;i++){ tag[i]^=tag[i-1]; s[i]^=tag[i]; gt[i]=1; if(s[i]!=t[i]){ int fl=0; if(i<=lasp){ if(i<lasp-1){ bool tg=1; for(int j=lasp+1;j<n-1;j++){ if((s[j-1]^(j-1<=lasp&&tg))==s[j+1]){ fl=j;break; } tg^=tag[j]; } } else if(i==lasp-1){ for(int j=lasp;j<n-1;j++){ if((s[j-1]^(j-1==lasp&&tag[lasp-1]^tag[lasp]))==s[j+1]){ fl=j;break; } } } else{ for(int j=lasp;j<n-1;j++){ if(s[j-1]==s[j+1]){ fl=j;break; } } } } else{ tag[i-1]=tag[i]=0;tag[i+1]=0; for(int j=i;j<n-1;j++){ if(s[j-1]==s[j+1]){ fl=j;break; } } } if(!fl){ cout<<"-1\n"; return ; } tag[i]^=1;s[i]^=1;tag[fl+1]^=1; ans+=fl-i+1; lasp=fl; } } cout<<ans<<"\n"; } bool Med; int main(){ cerr<<(&Mst-&Med)/1024.0/1024.0<<"??\n"; // freopen("yeah.in","r",stdin); // freopen("yeah.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0),cout.tie(0); // int sub,T; // cin>>sub>>T; int T=1; while(T--)solve(); return 0; }