Submission #1258068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258068		naneosmic	Mutating DNA (IOI21_dna)	C++20	100 / 100	55 ms	11336 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
#define int long long
#define endl "\n"
using namespace std;
vector<vector<int>>v;
map<string,int>m1;
map<int,pair<int,int>>m2;
void init(string a,string b){
    int n=a.size();
    m1["AA"]=6;
    m1["AC"]=0;
    m1["AT"]=1;
    m1["CA"]=2;
    m1["CC"]=6;
    m1["CT"]=3;
    m1["TA"]=4;
    m1["TC"]=5;
    m1["TT"]=6;
    m2[0]={0,1};
    m2[1]={0,2};
    m2[2]={1,0};
    m2[3]={1,2};
    m2[4]={2,0};
    m2[5]={2,1};
    v.resize(n+1,vector<int>(6,0));
    for(int i=0;i<n;i++){
        v[i+1]=v[i];
        string c;
        c.push_back(a[i]);
        c.push_back(b[i]);
        int num=m1[c];
        if(num!=6){
            v[i+1][num]++;
        }
    }
}
signed get_distance(signed x,signed y){
    y++;
    vector<int>pref=v[y];
    vector<int>cnt1(3,0);
    vector<int>cnt2(3,0);
    for(int i=0;i<6;i++){
        pref[i]-=v[x][i];
        pair<int,int>p=m2[i];
        cnt1[p.first]+=pref[i];
        cnt2[p.second]+=pref[i];
    }
    for(int i=0;i<3;i++){
        if(cnt1[i]!=cnt2[i]){
            return -1;
        }
    }
    int ans=0;
    int curr=min(pref[0],pref[2]);
    ans+=curr;
    pref[0]-=curr;
    pref[2]-=curr;
    curr=min(pref[3],pref[5]);
    ans+=curr;
    pref[3]-=curr;
    pref[5]-=curr;
    curr=min(pref[1],pref[4]);
    ans+=curr;
    pref[1]-=curr;
    pref[4]-=curr;
    ans+=2*(pref[0]+pref[1]);
    return ans;
}

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