Submission #1196942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196942		ivaziva	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	7176 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

#define MAXN 100001

int n;
int pref[2][3][MAXN],br[6][MAXN];
map<char,int> mapa;

void init(std::string a, std::string b)
{
    n=a.size();mapa['A']=0;mapa['C']=1;mapa['T']=2;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=2;j++) {pref[0][j][i]=pref[0][j][i-1];pref[1][j][i]=pref[1][j][i-1];}
        pref[0][mapa[a[i-1]]][i]++;pref[1][mapa[b[i-1]]][i]++;
        for (int j=0;j<=5;j++) br[j][i]=br[j][i-1];
        if (a[i-1]==b[i-1]) continue;
        if (a[i-1]=='A' and b[i-1]=='C') br[0][i]++;
        if (a[i-1]=='A' and b[i-1]=='T') br[1][i]++;
        if (a[i-1]=='C' and b[i-1]=='T') br[2][i]++;
        if (a[i-1]=='C' and b[i-1]=='A') br[3][i]++;
        if (a[i-1]=='T' and b[i-1]=='A') br[4][i]++;
        if (a[i-1]=='T' and b[i-1]=='C') br[5][i]++;
    }
}

int get_distance(int x,int y)
{
    x++;y++;int ans=0;
    if (pref[0][0][y]-pref[0][0][x-1]!=pref[1][0][y]-pref[1][0][x-1]) return -1;
    if (pref[0][1][y]-pref[0][1][x-1]!=pref[1][1][y]-pref[1][1][x-1]) return -1;
    if (pref[0][2][y]-pref[0][2][x-1]!=pref[1][2][y]-pref[1][2][x-1]) return -1;
    int br0=br[0][y]-br[0][x-1],br1=br[1][y]-br[1][x-1],br2=br[2][y]-br[2][x-1];
    int br3=br[3][y]-br[3][x-1],br4=br[4][y]-br[4][x-1],br5=br[5][y]-br[5][x-1];
    int value0=min(br0,br3);br0-=value0;br3-=value0;ans+=value0;
    int value1=min(br1,br4);br1-=value1;br4-=value1;ans+=value1;
    int value2=min(br2,br5);br2-=value2;br5-=value2;ans+=value2;
    ans+=2*max(br0,br3);return ans;
}

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