Submission #1142571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142571		redamoi	Mutating DNA (IOI21_dna)	C++20	0 / 100	228 ms	205500 KiB

dna

#include <bits/stdc++.h>
using namespace std;

vector<map<string,int>> MEM(1e6);

vector<vector<int>> freq1(1e6,vector<int>(3,0));
vector<vector<int>> freq2(1e6,vector<int>(3,0));

void init(string a, string b){
    string ax=a,bx=b;
    string A[6] = {"AT","TA","AC","CA","CT","TC"};
    string s;
    for(auto x:A)MEM[0][x]=0;
    for(int i=1;i<a.size();i++){
        s = "";
        s+=a[i];
        s+=b[i];
        for(auto x: A){
            if(x==s)MEM[i][x]=MEM[i-1][x]+1;
            else MEM[i][x]=MEM[i-1][x];
        }
        if(a[i]=='A')freq1[i][0]++;
        if(a[i]=='C')freq1[i][1]++;
        if(a[i]=='T')freq1[i][2]++;
        
        if(b[i]=='A')freq2[i][0]++;
        if(b[i]=='C')freq2[i][1]++;
        if(b[i]=='T')freq2[i][2]++;
    }
}



int get_distance(int x, int y){
    int ans =0, r =0;
    
    
    if(x==0){
        if(freq1[y][0]!=freq2[y][0] or freq1[y][1]!=freq2[y][1] or freq1[y][2]!=freq2[y][2]) return -1;
        
        ans+=min(MEM[y]["AT"],MEM[y]["TA"]);
        r+=max(MEM[y]["AT"],MEM[y]["TA"])-min(MEM[y]["AT"],MEM[y]["TA"]);
        ans+=min(MEM[y]["AC"],MEM[y]["CA"]);
        r+=max(MEM[y]["AC"],MEM[y]["CA"])-min(MEM[y]["AC"],MEM[y]["CA"]);
        ans+=min(MEM[y]["CT"],MEM[y]["TC"]);
        r+=max(MEM[y]["CT"],MEM[y]["TC"])-min(MEM[y]["CT"],MEM[y]["TC"]);
        ans+=r*2/3;
        return ans;
    }
    
    if(freq1[y][0]-freq1[x-1][0]!=freq2[y][0]-freq2[x-1][0] or freq1[y][1]-freq1[x-1][1]!=freq2[y][1]-freq2[x-1][1] or freq1[y][2]-freq1[x-1][2]!=freq2[y][2]-freq2[x-1][2]) return -1;


    ans+=min(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"]);
    r+=max(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"])-min(MEM[y]["AT"]-MEM[x-1]["AT"],MEM[y]["TA"]-MEM[x-1]["TA"]);
    ans+=min(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"]);
    r+=max(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"])-min(MEM[y]["AC"]-MEM[x-1]["AC"],MEM[y]["CA"]-MEM[x-1]["CA"]);
    ans+=min(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"]);
    r+=max(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"])-min(MEM[y]["CT"]-MEM[x-1]["CT"],MEM[y]["TC"]-MEM[x-1]["TC"]);
    ans+=r*2/3;
    return ans;
}

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