Submission #442073

#	Time	Username	Problem	Language	Result	Execution time	Memory
442073		daniel920712	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	8468 KiB

dna

#include "dna.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int con[5][5][100005]={0};
int con2[5][100005]={0};
int con3[5][100005]={0};
void init(string a,string b)
{
    int N=a.size(),i,j,k;
    for(i=0;i<N;i++)
    {
        for(j=0;j<3;j++)
        {
            con2[j][i+1]=con2[j][i];
            con3[j][i+1]=con3[j][i];
            for(k=0;k<3;k++) con[j][k][i+1]=con[j][k][i];
        }
        if(a[i]=='A')
        {
            con2[0][i+1]++;
            if(b[i]=='A') con[0][0][i+1]++;
            if(b[i]=='T') con[0][1][i+1]++;
            if(b[i]=='C') con[0][2][i+1]++;
        }
        if(a[i]=='T')
        {
            con2[1][i+1]++;
            if(b[i]=='A') con[1][0][i+1]++;
            if(b[i]=='T') con[1][1][i+1]++;
            if(b[i]=='C') con[1][2][i+1]++;
        }
        if(a[i]=='C')
        {
            con2[2][i+1]++;
            if(b[i]=='A') con[2][0][i+1]++;
            if(b[i]=='T') con[2][1][i+1]++;
            if(b[i]=='C') con[2][2][i+1]++;
        }
        if(b[i]=='A') con3[0][i+1]++;
        if(b[i]=='T') con3[1][i+1]++;
        if(b[i]=='C') con3[2][i+1]++;

    }
}

int get_distance(int x, int y)
{
    int ans=0;
    x++;
    y++;
    if(con2[0][y]-con2[0][x-1]!=con3[0][y]-con3[0][x-1]) return -1;
    if(con2[1][y]-con2[1][x-1]!=con3[1][y]-con3[1][x-1]) return -1;
    if(con2[2][y]-con2[2][x-1]!=con3[2][y]-con3[2][x-1]) return -1;
    ans+=min(con[0][1][y]-con[0][1][x-1],con[1][0][y]-con[1][0][x-1]);
    ans+=min(con[1][2][y]-con[1][2][x-1],con[2][1][y]-con[2][1][x-1]);
    ans+=min(con[0][2][y]-con[0][2][x-1],con[2][0][y]-con[2][0][x-1]);
    ans+=2*abs((con[0][1][y]-con[0][1][x-1])-(con[1][0][y]-con[1][0][x-1]));
	return ans;
}

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