제출 #1275795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275795		k12_khoi	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	34 ms	9716 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
char c[]={'A','C','T'};

int n,q,x,y,temp;
int pre[N][3][3],preTwo[N][3][3],cnt[3][3],dem[3][3];
string a,b;

void init(string a,string b)
{
    n=a.size();

    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<3;j++)
        for (int k=0;k<3;k++)
        {
            pre[i][j][k]=pre[i-1][j][k]+(a[i-1]!=b[i-1] and a[i-1]==c[j] and b[i-1]==c[k]);
            preTwo[i][j][k]=preTwo[i-1][j][k]+(a[i-1]!=b[i-1] and b[i-1]==c[j] and a[i-1]==c[k]);
        }
    }
}

int get_distance(int x,int y)
{
    x++;
    y++;

    for (int j=0;j<3;j++)
    {
        for (int k=0;k<3;k++)
        {
            cnt[j][k]=pre[y][j][k]-pre[x-1][j][k];
            dem[j][k]=preTwo[y][j][k]-preTwo[x-1][j][k];
        }

        if (cnt[j][0]+cnt[j][1]+cnt[j][2]!=dem[j][0]+dem[j][1]+dem[j][2]) return -1;
    }

    int ans=0;
    for (int j=0;j<3;j++)
    for (int k=0;k<3;k++)
    {
        temp=min(cnt[j][k],cnt[k][j]);

        cnt[j][k]-=temp;
        cnt[k][j]-=temp;

        ans+=temp;
    }

    temp=0;

    for (int j=0;j<3;j++)
    for (int k=0;k<3;k++)
    {
        ans+=cnt[j][k];
        temp+=cnt[j][k];
    }

    ans-=temp/3;

    return ans;
}

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