Submission #1265160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265160		tcmduc	Mutating DNA (IOI21_dna)	C++20	100 / 100	45 ms	12100 KiB

dna

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const long long oo=1e18;
const int mod=1e9+7;
bool bit(int x,int i){return (x>>i)&1;}
int n,q;
string a,b;
int cnt[3][100005][4],dif[100005][4][4];
void init(string a,string b)
{
    int n=a.size();a='0'+a,b='0'+b;
    for(int i=1;i<=n;i++)
    {
        if(a[i]=='A')a[i]='1';if(a[i]=='C')a[i]='2';if(a[i]=='T')a[i]='3';
        if(b[i]=='A')b[i]='1';if(b[i]=='C')b[i]='2';if(b[i]=='T')b[i]='3';
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2;j++)for(int k=1;k<=3;k++)cnt[j][i][k]=cnt[j][i-1][k];
        cnt[1][i][a[i]-'0']++;
        cnt[2][i][b[i]-'0']++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)for(int k=1;k<=3;k++)dif[i][j][k]=dif[i-1][j][k];
        dif[i][a[i]-'0'][b[i]-'0']++;
    }
}
int get_distance(int x,int y)
{
    x++,y++;
    for(int i=1;i<=3;i++)
        if(cnt[1][y][i]-cnt[1][x-1][i]!=cnt[2][y][i]-cnt[2][x-1][i])return -1;
    int kq=0,thua=0;
    for(int i=1;i<=3;i++)
    {
        for(int j=i+1;j<=3;j++)
        {
            int d1=dif[y][i][j]-dif[x-1][i][j];
            int d2=dif[y][j][i]-dif[x-1][j][i];
            kq+=min(d1,d2);
            thua+=max(d1,d2)-min(d1,d2);
        }
    }
    return kq+thua/3*2;
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16