Submission #1142395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142395		redacode	Mutating DNA (IOI21_dna)	C++20	0 / 100	209 ms	54032 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"};
    
    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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16