Submission #985438

#	Time	Username	Problem	Language	Result	Execution time	Memory
985438		user736482	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	10092 KiB

dna

#include<bits/stdc++.h>
using namespace std;
vector<int>pref[9],pref2[6];//a a  t t  c c  a t  t a   t c  c t  c a  a c

void init(string a,string b){
    for(int i=0;i<9;i++)
        pref[i].push_back(0);
    pref2[0].push_back(0);
    pref2[1].push_back(0);
    pref2[2].push_back(0);
    pref2[3].push_back(0);
    pref2[4].push_back(0);
    pref2[5].push_back(0);
    for(int i=0;i<(int)a.size();i++){
        pref[0].push_back(pref[0][i]);
        pref[1].push_back(pref[1][i]);
        pref[2].push_back(pref[2][i]);
        pref[3].push_back(pref[3][i]);
        pref[4].push_back(pref[4][i]);
        pref[5].push_back(pref[5][i]);
        pref[6].push_back(pref[6][i]);
        pref[7].push_back(pref[7][i]);
        pref[8].push_back(pref[8][i]);
        pref2[0].push_back(pref2[0][i]);
        pref2[1].push_back(pref2[1][i]);
        pref2[2].push_back(pref2[2][i]);
        pref2[3].push_back(pref2[3][i]);
        pref2[4].push_back(pref2[4][i]);
        pref2[5].push_back(pref2[5][i]);
    if(a[i]=='A')
        pref2[0][i+1]++;
    if(a[i]=='T')
        pref2[1][i+1]++;
    if(a[i]=='C')
        pref2[2][i+1]++;
    if(b[i]=='A')
        pref2[3][i+1]++;
    if(b[i]=='T')
        pref2[4][i+1]++;
    if(b[i]=='C')
        pref2[5][i+1]++;
    if(a[i]=='A' && b[i]=='A')
        pref[0][i+1]++;
    if(a[i]=='T' && b[i]=='T')
        pref[1][i+1]++;
    if(a[i]=='C' && b[i]=='C')
        pref[2][i+1]++;
    if(a[i]=='A' && b[i]=='T')
        pref[3][i+1]++;
    if(a[i]=='T' && b[i]=='A')
        pref[4][i+1]++;
    if(a[i]=='T' && b[i]=='C')
        pref[5][i+1]++;
    if(a[i]=='C' && b[i]=='T')
        pref[6][i+1]++;
    if(a[i]=='C' && b[i]=='A')
        pref[7][i+1]++;
    if(a[i]=='A' && b[i]=='C')
        pref[8][i+1]++;
}}

int get_distance(int x,int y){
    if(pref2[0][y+1]-pref2[0][x]!=pref2[3][y+1]-pref2[3][x] || pref2[1][y+1]-pref2[1][x]!=pref2[4][y+1]-pref2[4][x] || pref2[2][y+1]-pref2[2][x]!=pref2[5][y+1]-pref2[5][x])
        return -1;
    int answer=0;
    int dist=y-x+1;
    dist-=(pref[0][y+1]-pref[0][x]);
    dist-=(pref[1][y+1]-pref[1][x]);
    dist-=(pref[2][y+1]-pref[2][x]);
    dist-=2*min((pref[3][y+1]-pref[3][x]),(pref[4][y+1]-pref[4][x]));
    answer+=min((pref[3][y+1]-pref[3][x]),(pref[4][y+1]-pref[4][x]));
    dist-=2*min((pref[5][y+1]-pref[5][x]),(pref[6][y+1]-pref[6][x]));
    answer+=min((pref[5][y+1]-pref[5][x]),(pref[6][y+1]-pref[6][x]));
    dist-=2*min((pref[7][y+1]-pref[7][x]),(pref[8][y+1]-pref[8][x]));
    answer+=min((pref[7][y+1]-pref[7][x]),(pref[8][y+1]-pref[8][x]));
    answer+=dist*2/3;
    return answer;
}

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