Submission #1142398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142398		redacode	Mutating DNA (IOI21_dna)	C++20	100 / 100	421 ms	54544 KiB

dna

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

vector<map<string,int>> V(1e5);
string ax,bx;
void init(std::string a, std::string b) {
    ax=a,bx=b;
    int cnt =0;
    string s = "";
    s+=a[0];
    s+=b[0];
    string arr[6] = {"AT","TA","AC","CA","CT","TC"};
    for(auto x: arr){
        if(x==s){
           V[0][x]=1;
        }else{
           V[0][x]=0;
        }
    }
    for(int i=1;i<a.size();i++){
        s = "";
        s += a[i];
        s += b[i];
        //cout << s;
        for(auto x: arr){
            if(x==s){
                V[i][x]=V[i-1][x]+1;
                //c//out << x << V[i][x] <<endl;
            }else{
                V[i][x]=V[i-1][x];
            }
        }
    }

}

int get_distance(int x, int y) {
    int cnt =0;
    int r =0;
    string arr[6] = {"AT","TA","AC","CA","CT","TC"};
    
    if(x==0){
        int freqa1 = V[y]["AT"] + V[y]["AC"];
        int freqa2 = V[y]["TA"] + V[y]["CA"];
        int freqt1 = V[y]["TA"] + V[y]["TC"];
        int freqt2 = V[y]["CT"] + V[y]["AT"];
        int freqc1 = V[y]["CT"] + V[y]["CA"];
        int freqc2 = V[y]["TC"] + V[y]["AC"];
        if(freqa1!=freqa2 or freqt1!=freqt2 or freqc1!=freqc2) return -1;
    
    
        cnt += min(V[y]["AT"],V[y]["TA"]);
        r += max(V[y]["AT"],V[y]["TA"]) - min(V[y]["AT"],V[y]["TA"]);
        //cout << cnt<< " " << r<<endl;
        cnt += min(V[y]["AC"],V[y]["CA"]);
        r += max(V[y]["AC"],V[y]["CA"]) - min(V[y]["AC"],V[y]["CA"]);
        //cout << cnt<< " " << r<<endl;
        cnt += min(V[y]["CT"],V[y]["TC"]);
        r += max(V[y]["CT"],V[y]["TC"]) - min(V[y]["CT"],V[y]["TC"]);
        //cout << cnt<< " " << r<<endl;
        cnt += r*2/3;
        return cnt;
    }
    
    int freqa1 = V[y]["AT"]-V[x-1]["AT"] + V[y]["AC"]-V[x-1]["AC"];
    int freqa2 = V[y]["TA"]-V[x-1]["TA"] + V[y]["CA"]-V[x-1]["CA"];
    int freqt1 = V[y]["TA"]-V[x-1]["TA"] + V[y]["TC"]-V[x-1]["TC"];
    int freqt2 = V[y]["CT"]-V[x-1]["CT"] + V[y]["AT"]-V[x-1]["AT"];
    int freqc1 = V[y]["CT"]-V[x-1]["CT"] + V[y]["CA"]-V[x-1]["CA"];
    int freqc2 = V[y]["TC"]-V[x-1]["TC"] + V[y]["AC"]-V[x-1]["AC"];
    if(freqa1!=freqa2 or freqt1!=freqt2 or freqc1!=freqc2) return -1;
    
    
    cnt += min(V[y]["AT"]-V[x-1]["AT"],V[y]["TA"]-V[x-1]["TA"]);
    r += max(V[y]["AT"]-V[x-1]["AT"],V[y]["TA"]-V[x-1]["TA"]) - min(V[y]["AT"]-V[x-1]["AT"],V[y]["TA"]-V[x-1]["TA"]);
    //cout << cnt<< " " << r<<endl;
    cnt += min(V[y]["AC"]-V[x-1]["AC"],V[y]["CA"]-V[x-1]["CA"]);
    r += max(V[y]["AC"]-V[x-1]["AC"],V[y]["CA"]-V[x-1]["CA"]) - min(V[y]["AC"]-V[x-1]["AC"],V[y]["CA"]-V[x-1]["CA"]);
    //cout << cnt<< " " << r<<endl;
    cnt += min(V[y]["CT"]-V[x-1]["CT"],V[y]["TC"]-V[x-1]["TC"]);
    r += max(V[y]["CT"]-V[x-1]["CT"],V[y]["TC"]-V[x-1]["TC"]) - min(V[y]["CT"]-V[x-1]["CT"],V[y]["TC"]-V[x-1]["TC"]);
    //cout << cnt<< " " << r<<endl;
    cnt += r*2/3;
    return cnt;
}

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