| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1237667 | JelaByteEngineer | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5;
int prefa[MAXN][3], prefb[MAXN][3];
int dp[MAXN][3][3];
int cd (char c)
{
if (c=='A') return 0;
else if (c=='T') return 1;
else return 2;
}
void init (string a, string b)
{
int n=a.size();
for (int i=0; i<n; i++)
{
prefa[i][0]=(i>0? prefa[i-1][0]:0);
prefa[i][1]=(i>0? prefa[i-1][1]:0);
prefa[i][2]=(i>0? prefa[i-1][2]:0);
prefa[i][cd(a[i])]++;
prefb[i][0]=(i>0? prefb[i-1][0]:0);
prefb[i][1]=(i>0? prefb[i-1][1]:0);
prefb[i][2]=(i>0? prefb[i-1][2]:0);
prefb[i][cd(b[i])]++;
}
for (int i=0; i<n; i++)
{
dp[i][cd(a[i])][cd(b[i])]=(i>0? dp[i-1][cd(a[i])][cd(b[i])]:0)+1;
for (int j=0; j<3; j++)
{
for (int k=0; k<3; k++)
{
if (j!=cd(a[i]) || k!=cd(b[i])) dp[i][j][k]=(i>0? dp[i-1][j][k]:0);
}
}
}/*
for (int i=0; i<n; i++)
{
cout<<"i je: "<<i<<endl;
for (int j=0; j<3; j++)
{
for (int k=0; k<3; k++)
{
cout<<"j i k su: "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
}
}
}*/
}
int get_distance (int x, int y)
{
if (prefa[y][0]-(y>0? prefa[x-1][0]:0)!=prefb[y][0]-(y>0? prefb[x-1][0]:0)
|| prefa[y][1]-(y>0? prefa[x-1][1]:0)!=prefb[y][1]-(y>0? prefb[x-1][1]:0)
|| prefa[y][2]-(y>0? prefa[x-1][2]:0)!=prefb[y][2]-(y>0? prefb[x-1][2]:0
)) return -1;
int dp1[3][3];
int ans=0;
for (int i=0; i<3; i++)
{
for (int j=i+1; j<3; j++)
{
//cout<<"i i j su: "<<i<<" "<<j<<endl;
int minmin=min(dp[y][i][j]-(y>0? dp[x-1][i][j]:0), dp[y][j][i]-(y>0? dp[x-1][j][i]:0));
/*cout<<"minmin je: "<<minmin<<endl;
cout<<"dp i dp su: "<<dp[y][i][j]-(y>0? dp[x-1][i][j]:0)<<" "<<dp[y][j][i]-(y>0? dp[x-1][j][i]:0)<<endl;*/
ans+=minmin;
dp1[i][j]=dp[y][i][j]-(y>0? dp[x-1][i][j]:0)-minmin;
dp1[j][i]=dp[y][j][i]-(y>0? dp[x-1][j][i]:0)-minmin;
//cout<<"novi dp1 i dp1 su: "<<dp1[i][j]<<" "<<dp1[j][i]<<endl;
}
}
vector <vector <int>> perm(6);
perm[0]={0, 1, 2}; perm[1]={0, 2, 1}; perm[2]={1, 0, 2}; perm[3]={1, 2, 0}; perm[4]={2, 0, 1}; perm[5]={2, 1, 0};
for (int i=0; i<6; i++)
{
int x1=perm[i][0], y1=perm[i][1], z1=perm[i][2];
int minmin=min({dp1[x1][y1], dp1[y1][z1], dp1[z1][x1]});
ans+=2*minmin;
dp1[x1][y1]-=minmin; dp1[y1][z1]-=minmin; dp1[z1][x1]-=minmin;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, q; cin>>n>>q;
string a, b; cin>>a>>b;
init(a, b);
while (q--)
{
int x, y; cin>>x>>y;
cout<<get_distance(x, y)<<endl;
}
return 0;
}