Submission #536808

#	Time	Username	Problem	Language	Result	Execution time	Memory
536808		MurotY	Mutating DNA (IOI21_dna)	C++17	100 / 100	824 ms	30556 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
const int N=1e5+7;
string a, b, a1, b1;
int n;
int dp[N][30], dp1[N][30];
int dp2[N];
int v[10][N];
vector <string> v1;
map <string,int> mp;
void init(string a0, string b0) {
    a = a0;
    b = b0;
    a1 = a;
    b1 = b;
    n = a.length();
   for (int i=0;i<=n;i++) {
        for (int j=0;j<=26;j++) dp[i][j]=dp1[i][j]=0;
        }


    mp["AC"]=1; mp["AT"]=2;
    mp["CA"]=3; mp["CT"]=4;
    mp["TA"]=5; mp["TC"]=6;

    v1.push_back("AC"); v1.push_back("AT");
    v1.push_back("CA"); v1.push_back("CT");
    v1.push_back("TA"); v1.push_back("TC");

    for (int i=0;i<n;i++){
        string s="";
        s=s+a[i];
        s=s+b[i];
        for (int j=0;j<6;j++){
            if (v1[j] == s) v[mp[v1[j]]][i+1]=v[mp[v1[j]]][i]+1;
            else v[mp[v1[j]]][i+1]=v[mp[v1[j]]][i];
        }
    }

    for (int i=0;i<n;i++){
        if (a[i] != b[i]) dp2[i+1]=dp2[i]+1;
        else dp2[i+1]=dp2[i];
    }

    for (int i=0;i<n;i++){
        for (char c='A';c<='Z';c++){
            if (a[i] == c) dp[i+1][c-'A']=dp[i][c-'A']+1;
            else dp[i+1][c-'A']=dp[i][c-'A'];
            if (b[i] == c) dp1[i+1][c-'A']=dp1[i][c-'A']+1;
            else dp1[i+1][c-'A']=dp1[i][c-'A'];
        }
    }
}
int get_distance(int x, int y) {
    a = a1;
    b = b1;
   for (int i = 0; i < 26; i++){
            if (dp[y+1][i]-dp[x][i] != dp1[y+1][i]-dp1[x][i]) return -1;
    }

    int arr[10];
    for (int i=0;i<6;i++){
        int q=v[mp[v1[i]]][y+1]-v[mp[v1[i]]][x];
        arr[i+1]=q;
    }
    int mn=min(arr[1], arr[3]);
    int mn1=min(arr[2], arr[5]);
    int mn2=min(arr[4], arr[6]);
    int q=dp2[y+1]-dp2[x];
    int ans=0;
    ans=mn+mn1+mn2;
    q-=2*(mn+mn1+mn2);
    ans+=(q*2)/3;
    return ans;
}

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