제출 #977375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977375		sstojilkovic19	DNA 돌연변이 (IOI21_dna)	C++17	71 / 100	1539 ms	7192 KiB

dna

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

using namespace std;
string aa, bb;
int n = 100010;

vector< vector<int> >pref(10, vector<int>(n, 0));

void init(std::string a, std::string b) {
    aa=" "+a;
    bb=" "+b;
    n = a.length();

    /*
    0 uk
    1 AT
    2 TA
    3 AC
    4 CA
    5 TC
    6 CT
    TAC
    CTA
    */
    a = " " + a;
    b = " " + b;

    for(int i = 0; i<=6; i++)
    {
        pref[i][0]=0;
        for(int j = 1; j<=n; j++)
        {
            pref[i][j]=pref[i][j-1];
            if(i==0 && a[j]!=b[j])pref[i][j]++;
            else if(i==1 && a[j]=='A' && b[j]=='T')pref[i][j]++;
            else if(i==2 && a[j]=='T' && b[j]=='A')pref[i][j]++;
            else if(i==3 && a[j]=='A' && b[j]=='C')pref[i][j]++;
            else if(i==4 && a[j]=='C' && b[j]=='A')pref[i][j]++;
            else if(i==5 && a[j]=='T' && b[j]=='C')pref[i][j]++;
            else if(i==6 && a[j]=='C' && b[j]=='T')pref[i][j]++;
        }
    }
}

int get_distance(int x, int y)
{
    x++;
    y++;
    map<char, int>m1, m2;
    for(int i = x; i<=y; i++)
    {
        m1[aa[i]]++;
        m2[bb[i]]++;
    }
    if(m1['A']!=m2['A'] || m1['T']!=m2['T'] || m1['C']!=m2['C'])
    {
        return -1;
    }

	int cnt = 0;
	cnt += min(pref[1][y]-pref[1][x-1], pref[2][y]-pref[2][x-1]);
	//cout<<cnt<<"\n";
	cnt += min(pref[3][y]-pref[3][x-1], pref[4][y]-pref[4][x-1]);
	//cout<<cnt<<"\n";
	cnt+= min(pref[5][y]-pref[5][x-1], pref[6][y]-pref[6][x-1]);
	int uk = pref[0][y]-pref[0][x-1];
	int ans = cnt + 2*(uk - 2*cnt)/3;

    //
	return ans;
}

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